4179 : 불!

출처 : https://www.acmicpc.net/problem/4179

---

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

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

불은 각 지점에서 네 방향으로 확산된다. 

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

 각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이난 공간

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

출력

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

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다. 

---

접근

• 탈출 여부를 위해, map의 크기를 R+2, L+2으로 늘려주었다. 
• 입력값에 따라, map에 int로 변경하여 넣어주었다.
• 지훈이의 위치를 먼저 queue에 넣고, 그 다음 불의 위치를 queue에 넣는다. 
• BFS함수는 지훈이의 위치에 대해 먼저 수행하고, 그다음 불의 위치에 대해 수행한다. (지훈->불->지훈->불 ...)

---

코드

package beak;
 
import java.util.*;
import java.io.*;
 
class Fire {
    int x, y;
 
    public Fire(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
 
public class Main {
 
    static int R, C;
    static int[][] map;
    static int[][] visit;
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, -1, 0, 1 };
 
    public static int BFS() {
        Queue<Fire> q = new LinkedList<Fire>();
        for (int i = 0; i < R + 2; i++) {
            for (int j = 0; j < C + 2; j++) {
                if (map[i][j] == 1) {
                    q.add(new Fire(i, j));
                }
            }
        }
        for (int i = 0; i < R + 2; i++) {
            for (int j = 0; j < C + 2; j++) {
                if (map[i][j] == 2) {
                    q.add(new Fire(i, j));
                }
            }
        }
 
        while (!q.isEmpty()) {
            Fire tmp = q.poll();
            int X = tmp.x;
            int Y = tmp.y;
 
            if (map[X][Y] == 1) {
                for (int i = 0; i < 4; i++) {
                    int nextX = X + dx[i];
                    int nextY = Y + dy[i];
                    if (map[nextX][nextY] == -2) {
                        return visit[X][Y];
                    }
                    if (nextX >= 0 && nextY >= 0 && nextX < R + 2 && nextY < C + 2) {
                        if (map[nextX][nextY] == 0 && visit[nextX][nextY] == 0) {
                            map[nextX][nextY] = map[X][Y];
                            visit[nextX][nextY] = visit[X][Y] + 1;
                            q.add(new Fire(nextX, nextY));
                        }
                    }
                }
            }
 
            if (map[X][Y] == 2) {
                for (int i = 0; i < 4; i++) {
                    int nextX = X + dx[i];
                    int nextY = Y + dy[i];
 
                    if (nextX >= 0 && nextY >= 0 && nextX < R + 2 && nextY < C + 2) {
                        if (map[nextX][nextY] != 3 && visit[nextX][nextY] >= 0) {
                            map[nextX][nextY] = map[X][Y];
                            visit[nextX][nextY] = -1;
                            q.add(new Fire(nextX, nextY));
                        }
                    }
                }
            }
        }
        return -1;
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
 
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
 
        map = new int[R + 2][C + 2];
        visit = new int[R + 2][C + 2];
 
        for (int i = 0; i < R + 2; i++) {
            for (int j = 0; j < C + 2; j++) {
                if (i == 0 || j == 0 || i == R + 1 || j == C + 1) {
                    map[i][j] = -2;
                    visit[i][j] = -2;
                }
            }
        }
 
        int k = 0;
        for (int i = 1; i <= R; i++) {
            char[] c = br.readLine().toCharArray();
            for (int j = 1; j <= C; j++) {
                if (c[k] == '#') {
                    map[i][j] = 3;
                    visit[i][j] = -3;
                } else if (c[k] == 'J') {
                    map[i][j] = 1;
                    visit[i][j] = 1;
                } else if (c[k] == '.') {
                    map[i][j] = 0;
                    visit[i][j] = 0;
                } else {
                    map[i][j] = 2;
                    visit[i][j] = -1;
                }
                k++;
                if (k == c.length) {
                    k = 0;
                    break;
                }
            }
        }
 
        int ans = BFS();
 
        if (ans == -1)
            bw.write("IMPOSSIBLE\n");
        else
            bw.write(ans + "\n");
 
        bw.flush();
        br.close();
    }
 
}