[백준]#4179 불!

문제

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

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

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

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

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

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

입력

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

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

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

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

출력

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

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

예제 입력 1

4 4
####
#JF#
#..#
#..#

예제 출력 1

3

풀이

이 문제는 전에 풀었던 탈출 문제와 비슷한 문제여서 BFS 알고리즘을 이용해서 조금 변형해서 풀었다.

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

public class Main {
    static int R;
    static int C;
    static char[][] map;
    static Queue<Pair> fire = new LinkedList<>();
    static boolean[][] fireVisited;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        R = Integer.parseInt(str[0]);
        C = Integer.parseInt(str[1]);
        map = new char[R][C];
        visited = new boolean[R][C];
        fireVisited = new boolean[R][C];
        Pair current = new Pair(0, 0, 0);

        for(int i=0; i<R; i++) {
            String input = br.readLine();

            for(int j=0; j<C; j++) {
                map[i][j] = input.charAt(j);

                if(map[i][j]=='J')
                    current = new Pair(i, j, 0);

                if(map[i][j]=='F') {
                    fire.add(new Pair(i, j, 0));
                    fireVisited[i][j]=true;
                }
            }
        }

        if(current.x==0 || current.x==R-1 || current.y==0 || current.y==C-1)
            System.out.println(1);

        else {
            int result = bfs(current);

            if(result<0)
                System.out.println("IMPOSSIBLE");
            else
                System.out.println(result+1);
        }
    }

    static int bfs(Pair p) {
        Queue<Pair> queue = new LinkedList<>();
        queue.add(p);
        visited[p.x][p.y]=true;

        while(!queue.isEmpty()) {
            int s = queue.size();
            fireMove();

            for(int k=0; k<s; k++) {
                Pair current = queue.poll();

                for(int i=0; i<4; i++) {
                    int X = current.x+dx[i];
                    int Y = current.y+dy[i];
                    int cnt = current.cnt+1;

                    if(X>=0 && Y>=0 && X<R && Y<C && map[X][Y]=='.' && !fireVisited[X][Y] && !visited[X][Y]) {
                        if(X==0 || Y==0 || X==R-1 || Y==C-1)
                            return cnt;
                        visited[X][Y]=true;
                        queue.add(new Pair(X, Y, cnt));
                    }
                }
            }
        }
        return -1;
    }

    static void fireMove() {
        int s =fire.size();

        for(int j=0; j<s; j++) {
            Pair p = fire.poll();

            for(int i=0; i<4; i++) {
                int X = p.x+dx[i];
                int Y = p.y+dy[i];
                int cnt = p.cnt+1;

                if(X>=0 && Y>=0 && X<R && Y<C && map[X][Y]=='.' && !fireVisited[X][Y]) {
                    fireVisited[X][Y]=true;
                    fire.add(new Pair(X, Y, cnt));
                }
            }
        }
    }

    static class Pair {
        int x;
        int y;
        int cnt;

        public Pair(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
}