4179 불 Java

2023. 10. 30. 14:56· Problem Solving/백준

4179번: 불!

문제를 꼼꼼히 읽는 습관이 필요하다고 느낀 문제
구현 자체는 BFS를 활용하는 것이라 크게 어렵지 않았는데 문제 조건 체크하는 게 좀 빡셌다.
나를 괴롭혔던 조건은 다음과 같다.

  • J는 입력에서 하나만 주어진다.
    -> 초반에 지훈이 위치와 불의 위치를 각각 배열에 담아서 Queue에 넘겼는데 하나의 불 밖에 담지 못해 문제가 생겼다. 또한, 불이 없는 경우에도 문제가 생겼는데 while문의 조건을 !.jq.isEmpty()&&!fq.isEmpty()로 설정해서 불이 없을 때도 탈출 불가를 띄웠다.
  • 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.
    -> y가 0이거나 x가 0일 때도 가장자리에 해당하기 때문에 탈출이 가능하다.
  • 그리고 좀 어이없게 실수한 부분은 시작하자마자 탈출하면 0초가 아닌 1초였다

풀이 자체는 레벨 단위 탐색으로 1초마다 지훈이와 불이 움직이도록 했다.

  • 불의 경우 지훈이와 다르게 불이 이동한 자리는 먼저 방문시켰다.
    이렇게 함으로써 다음 지훈이 움직일 때 이미 불이 난 경우 움직일 수 없도록 했다.

핵심은 불과 지훈이가 다른 큐에서 움직인다는 점인 것 같다.

import java.io.*;
import java.util.*;
public class Main {
static Queue<int[]> jq = new ArrayDeque<>(), fq = new ArrayDeque<>();
static int[] dy = {-1, 1, 0, 0}, dx = {0, 0, -1, 1};
static int R, C, ans = 0;
static char[][] map;
static boolean[][][] v;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new char[R][C];
v = new boolean[2][R][C];
for (int i = 0; i < R; i++) {
String s = br.readLine();
for (int j = 0; j < C; j++) {
map[i][j] = s.charAt(j);
if (map[i][j] == 'J') {
jq.add(new int[]{i, j});
} else if (map[i][j] == 'F') {
fq.add(new int[]{i, j});
}
}
}
ans = BFS();
if(ans == -1) System.out.println("IMPOSSIBLE");
else System.out.println(ans);
br.close();
}
static int BFS() {
int time = 1;
int[] jihun = jq.peek();
// 시작부터 출구면 끝
if(jihun[0] == R - 1 || jihun[1] == C - 1 || jihun[0] == 0 || jihun[1] == 0) return time;
// 먼저 불은 다 방문 처리
for(int[] temp : fq){
v[1][temp[0]][temp[1]] = true;
}
while (!jq.isEmpty()) {
int jSize = jq.size(), fSize = fq.size();
for (int i = 0; i < jSize; i++) {
int[] jTemp = jq.poll();
// 탈출 조건은 맵 끝 라인만이 아님 -> 가장자리일 경우 모두 탈출 가능
if ((jTemp[0] == R - 1 || jTemp[1] == C - 1
|| jTemp[0] == 0 || jTemp[1] == 0) && !v[1][jTemp[0]][jTemp[1]]) return time;
if (v[0][jTemp[0]][jTemp[1]] || v[1][jTemp[0]][jTemp[1]]) continue;
v[0][jTemp[0]][jTemp[1]] = true;
for (int j = 0; j < 4; j++) {
int ny = jTemp[0] + dy[j], nx = jTemp[1] + dx[j];
if (ny >= R || nx >= C || ny < 0 || nx < 0
|| v[0][ny][nx] || map[ny][nx] != '.') continue;
jq.add(new int[]{ny, nx});
}
}
for (int i = 0; i < fSize; i++) {
int[] fTemp = fq.poll();
for (int j = 0; j < 4; j++) {
int ny = fTemp[0] + dy[j], nx = fTemp[1] + dx[j];
// 이미 불이 난 곳이거나 벽이면 안감.
if(ny >= R || nx >= C || ny < 0 || nx < 0
|| v[1][ny][nx] || map[ny][nx] == '#') continue;
v[1][ny][nx] = true;
fq.add(new int[]{ny, nx});
}
}
time++;
}
return -1;
}
}

 

'Problem Solving > 백준' 카테고리의 다른 글

12865 : 평범한 배낭 - Java  (0) 2024.01.08
1106 : 호텔 Java  (0) 2024.01.07
30869 : 빨리기다리기 Java  (0) 2023.12.18
5639 : 이진 검색 트리 Java  (0) 2023.11.05
'Problem Solving/백준' 카테고리의 다른 글
  • 12865 : 평범한 배낭 - Java
  • 1106 : 호텔 Java
  • 30869 : 빨리기다리기 Java
  • 5639 : 이진 검색 트리 Java
greatwhite
greatwhite
greatwhite
우직하게
greatwhite
전체
오늘
어제
  • 분류 전체보기
    • Projects
      • 스위프] Woory
    • Python
    • Java
      • Spring
    • JPA
    • Problem Solving
      • 백준
      • 프로그래머스
    • Today I Learned

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • BFS
  • 스프링
  • 백준
  • 자바
  • dfs
  • pigeonhole principle
  • 다익스트라
  • knapsack
  • 그리디
  • 오블완
  • 티스토리챌린지
  • backtracking
  • MVC
  • @default
  • 비트마스킹
  • erd 문법
  • spring
  • dp
  • 프로그래머스
  • math
  • 파이썬
  • implementation
  • Java
  • Mermaid
  • vi
  • JPA
  • sql
  • 롬복
  • python
  • Euclidean

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
greatwhite
4179 불 Java
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.