[BOJ]4179 - 불!(G4)

문제 링크

4179-불!

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다.
단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
다음 입력으로 R줄동안 각각의 미로 행이 주어진다.
각각의 문자들은 다음을 뜻한다.

#: 벽
.: 지나갈 수 있는 공간
J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
F: 불이 난 공간
J는 입력에서 하나만 주어진다.

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.
지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

문제 풀이

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.
즉, 지훈이와 불은 매 분 동시에 움직인다 는 것이다.

이 부분을 제대로 처리하지 못하면, 불이 움직여서 지훈이는 가지 못하는 위치지만, 큐에는 지훈이가 움직인걸로 처리되어 오류가 발생할 수도 있다.
그렇기 때문에, 먼저 불을 옮겨주고 지훈이가 옮겨가는 식으로 코드를 진행

두 개의 큐를 가지고 진행해야하는데, 같은 시간대에 각자의 큐에 들어간 갯수만큼을 빼주는 방식으로 한번당 움직일 수 있는 불과 지훈의 경로를 파악

그래서 지훈이 경계값 밖으로 나가면 결과값 출력
지훈의 경로 큐가 비어있으면 더 이상 움직일 수 없다는 의미이기때문에 IMPOSSIBLE 출력

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N, M, result;
    static char[][] maps;
    static boolean[][] visited;
    static Queue<int[]> jqueue, fqueue;
    
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        maps = new char[N][M];
        jqueue = new LinkedList<>();
        fqueue = new LinkedList<>();
        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            for (int j = 0; j < M; j++) {
                maps[i][j] = str.charAt(j);
                if(maps[i][j] == 'J') jqueue.add(new int[]{i, j});
                if(maps[i][j] == 'F') fqueue.add(new int[]{i, j});
            }
        }
        bfs();
    }

    static void bfs() {
        while (true) {
            result++;

            int fsize = fqueue.size();
            while (fsize > 0) {
                fsize--;
                int[] cur = fqueue.poll();

                for (int i = 0; i < 4; i++) {
                    int nx = cur[0] + dx[i];
                    int ny = cur[1] + dy[i];

                    if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
                    if (maps[nx][ny] == 'J' || maps[nx][ny] == '.') {
                        fqueue.add(new int[]{nx, ny});
                        maps[nx][ny] = 'F';
                    }
                }
            }

            int jsize = jqueue.size();
            while (jsize > 0) {
                jsize--;
                int[] cur = jqueue.poll();

                for (int i = 0; i < 4; i++) {
                    int nx = cur[0] + dx[i];
                    int ny = cur[1] + dy[i];

                    if (nx < 0 || nx >= N || ny < 0 || ny >= M) {
                        System.out.println(result);
                        return;
                    }
                    if (maps[nx][ny] == '.') {
                        jqueue.add(new int[]{nx, ny});
                        maps[nx][ny] = 'J';
                    }
                }
            }
            if (jqueue.isEmpty()) {
                System.out.println("IMPOSSIBLE");
                return;
            }
        }
    }
}