Skip to main content

4179 - 불!

info
  • 문제 보기: 4179 - 불!
  • 소요 시간: 47분 19초
  • 풀이 언어: java
  • 체감 난이도: 3️⃣~4️⃣
  • 리뷰 횟수: ✅

풀이 키워드​

스포주의

bfs


풀이 코드​

info
  • 메모리: 58084 KB
  • 시간: 520 ms
import java.io.*;
import java.util.*;

public class Main
{
    static int r, c;
    static int[][] miro;
    static boolean[][] fvisited;
    static boolean[][] jvisited;
    static Deque<int[]> fq = new ArrayDeque<>();
    static Deque<int[]> jq = new ArrayDeque<>();
    static int[] dy = {-1, 0, 0, 1};
    static int[] dx = {0, -1, 1, 0};
    
    public static int bfs() {
        // queue init was done in input()
        int time = 1;
        
        while (!jq.isEmpty()) { // until J evacuate
            while (!fq.isEmpty() && fq.peek()[2] == time) {
                int[] fpos = fq.pop();
                for (int d = 0; d < 4; ++d) {
                    int nfy = fpos[0] + dy[d];
                    int nfx = fpos[1] + dx[d];
                    if (nfy < 0 || r <= nfy || nfx < 0 || c <= nfx) continue; // out of bound
                    if (fvisited[nfy][nfx] || miro[nfy][nfx] == 1) continue;
                    fvisited[nfy][nfx] = true;
                    fq.add(new int[]{nfy, nfx, time+1});
                }
            }
            
            while (!jq.isEmpty() && jq.peek()[2] == time) {
                int[] jpos = jq.pop();
                for (int d = 0; d < 4; ++d) {
                    int njy = jpos[0] + dy[d];
                    int njx = jpos[1] + dx[d];
                    if (njy < 0 || r <= njy || njx < 0 || c <= njx) return time; // evacuate
                    if (fvisited[njy][njx] || jvisited[njy][njx] || miro[njy][njx] == 1) continue;
                    jvisited[njy][njx] = true;
                    jq.add(new int[]{njy, njx, time+1});
                }
            }
            ++time;
        }
        
        return -1;
    }
    
    public static void main(String[] args) throws IOException {
        input();
        int ans = bfs();
        System.out.println(ans == -1 ? "IMPOSSIBLE" : ans);
    }
    
    public static void input() 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());
        miro = new int[r][c];
        fvisited = new boolean[r][c];
        jvisited = new boolean[r][c];
        
        for (int i = 0; i < r; ++i) {
            char[] line = br.readLine().toCharArray();
            for (int j = 0; j < c; ++j) {
                miro[i][j] = line[j] == '#' ? 1 : 0;
                if (line[j] == 'J') {
                    jq.add(new int[]{i, j, 1});
                    jvisited[i][j] = true;
                }
                else if (line[j] == 'F') {
                    fq.add(new int[]{i, j, 1});
                    fvisited[i][j] = true;
                }
            }
        }
    }
}

풀이 해설​

구현은 어렵지 않은데 corner case 종합 선물세트같은 문제이다.

주어진 맵에서 지훈이가 불에 안타고 무사 탈출이 가능한지 닥터 스트레인지마냥 탐색해보아야 한다.

최단 시간을 출력해야하므로 bfs를 사용해야 한다는 것은 자동으로 떠오르게 된다.


⚠️ 실수하기 쉬운 반례​

다음의 케이스를 조심해야 한다.


CASE 1

불은 0 ~ n개가 주어질 수 있다.

J는 입력에서 하나만 주어진다.

👉 문제를 잘 읽자. J는 조건을 명확하게 했지만 F에 대해선 아무 말이 없다. (=낚시질)

5 5
#####
#J.F#
#..F#
#...#
#...#
정답
4

5 5
#####
#J.F#
#...#
#..F#
#...#
정답
IMPOSSIBLE

CASE 2

불과 지훈이가 같은 지점에 동시 도착하면 지훈이가 타버린다.

불 bfs를 먼저 진행해야할까, 지훈 bfs를 먼저 진행해야할까?

불을 먼저 진행하는 것이 좋다. 어차피 동시 도착하는 지점은 무효한 탈출경로가 되기 때문에

애당초 bfs 큐에 안넣는 것이 최적의 선택일 것이다.


CASE 3

시작부터 지훈이가 경계에 있는 경우

풀이 코드처럼

if (njy < 0 || r <= njy || njx < 0 || c <= njx) return time; // evacuate

이렇게 탈출 조건을 out-bound 기준으로 세웠다면 시작부터 경계에 있는 경우를 따로 처리해줄 필요가 없다.

하지만 y가 0 또는 r-1, x가 0 또는 c-1 인 경우로 탈출 조건을 세웠다면, 이를 ny, nx로 판단하면 안되기에

bfs에서 while 들어가기 전 초기값을 한번 검사해주는 별도의 로직이 필요해진다.

1 3
J#F
정답
1

메모​

  • 더블 bfs는 웬만하면 while 안에 while 2개 돌아간다고 템플릿 잡아놓기
  • 다시는 while (!q.isEmpty()) 로직 내부에 while (q.peek()[2] == ...) 로직 넣는 실수하지 마쇼 이건 경고요...
    • q.pop() 하다가 peek에서 널익셉션 터짐 T~T