4179 불 Java

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;
    }

}