(4179) 불! (Java)

문제

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

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

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

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

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

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

입력

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

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

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

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

출력

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

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

예제 입력 1

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

예제 출력 1

3

출처

Contest > Waterloo's local Programming Contests > 13 June, 2009 B번

문제의 오타를 찾은 사람: apjw6112, vl0612
데이터를 추가한 사람: chayhyeon, dldmswp3, duno72, ktyong1225, myyh1234, pill27211
잘못된 번역을 찾은 사람: jh05013
문제를 번역한 사람: lyzqm

알고리즘 분류

그래프 이론
그래프 탐색
너비 우선 탐색

Solution

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ4179 {
    public static int r;
    public static int c;
    public static char[][] maze;
    public static int[][] fire;
    public static int[][] jihoon;

    public static class Pair {
        int x, y;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        r = Integer.parseInt(st.nextToken());   // 미로의 행
        c = Integer.parseInt(st.nextToken());   // 미로의 열

        // 미로, 불, 지훈 공간 생성
        // 불, 지훈 int 형으로 생성하는 이유는 몇분이 지났는지 함께 체크하기 위함
        maze = new char[r][c];
        fire = new int[r][c];
        jihoon = new int[r][c];

        // 불, 지훈 초기 세팅 -1 (불은 안났고, 지훈이는 아직 미로에 안들어온 것으로 세팅)
        for(int i = 0; i < r; i++) {
            Arrays.fill(fire[i], -1);
            Arrays.fill(jihoon[i], -1);
        }
        
        // 불, 지훈의 좌표 탐색을 위한 큐 생성
        Queue<Pair> qF = new LinkedList<Pair>();
        Queue<Pair> qJ = new LinkedList<Pair>();

        // 입력을 받아 공간을 세팅
        for(int i = 0; i < r; i++) {
            String[] str = br.readLine().split("");
            for(int j = 0; j < c; j++) {
                // maze : 미로 세팅
                maze[i][j] = str[j].charAt(0);

                // fire : 불이 시작되는 곳 세팅
                if(maze[i][j] == 'F') {
                    qF.offer(new Pair(i, j));
                    fire[i][j] = 0;
                }

                // jihoon : 지훈이의 시작 위치 세팅
                if(maze[i][j] == 'J') {
                    // 지훈이의 시작 위치가 가장자리인 경우 바로 탈출 (1분)
                    if(isEdge(i, j)) {
                        System.out.println(1);
                        return;
                    }

                    qJ.offer(new Pair(i, j));
                    jihoon[i][j] = 0;
                }
            }
        }
        br.close();

        // 미로찾기 시작
        bw.write(findEscape(qF, qJ));
        bw.flush();
        bw.close();

    }

    public static boolean isNotRange(int x, int y) {
        if(x < 0 || x >= r || y < 0 || y >= c) return true;
        else return false;
    }

    public static boolean isEdge(int x, int y) {
        if(x == 0 || x == r-1 || y == 0 || y == c-1) return true;
        else return false;
    }

    public static String findEscape(Queue<Pair> qF, Queue<Pair> qJ) {

        // 불의 번짐과 지훈의 이동을 위한 델타값 세팅 (하, 좌, 상, 우)
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, -1, 0, 1};

        // 미로찾기 시작
        // 불의 번짐
        while(!qF.isEmpty()) {
            Pair pollCellF = qF.poll();      // 탐색할 칸 poll

            // 인접한 칸 탐색
            for(int k = 0; k < 4; k++) {
                int nx = pollCellF.x + dx[k];
                int ny = pollCellF.y + dy[k];

                // 인접한 칸이 미로 범위를 벗어나거나, 벽이거나, 이미 불이 나있으면 skip
                if(isNotRange(nx, ny) || maze[nx][ny] == '#' || fire[nx][ny] != -1) continue;

                // 불이 번짐
                qF.offer(new Pair(nx, ny));
                fire[nx][ny] = fire[pollCellF.x][pollCellF.y] + 1;
            }
        }

        // 지훈 이동
        while(!qJ.isEmpty()) {
            Pair pollCellJ = qJ.poll();     // 탐색할 칸 poll

            // 지훈이가 이동 시 도착 시간
            int time = jihoon[pollCellJ.x][pollCellJ.y] + 1;

            // 지훈이 이동 중 가장자리에 도달하면 탈출
            if(isEdge(pollCellJ.x, pollCellJ.y)) return String.valueOf(time);

            // 인접한 칸 탐색
            for(int k = 0; k < 4; k++) {
                int nx = pollCellJ.x + dx[k];
                int ny = pollCellJ.y + dy[k];

                // 인접한 칸이 미로 범위를 벗어나거나, 벽이거나,
                // 지훈이 도착 시간 전에 이미 불이 나있거나(-1이 아닌것중에서 비교해줘야함 불이 아예 안난 곳은 지훈이는 갈 수 있음)
                // , 지훈이가 이미 지나온 곳이면 skip
                if(isNotRange(nx, ny) || maze[nx][ny] == '#'
                        || (fire[nx][ny] != -1 && fire[nx][ny] <= time)
                        || jihoon[nx][ny] != -1) continue;

                // 지훈 이동
                qJ.offer(new Pair(nx, ny));
                jihoon[nx][ny] = jihoon[pollCellJ.x][pollCellJ.y] + 1;
            }
        }

        // 이동을 끝마쳤는데도 탈출을 하지 못했으므로
        return "IMPOSSIBLE";
    }
}

Feedback

• 불을 먼저 번지게 한 후, 지훈이가 이동하면서 불이 해당 칸에 번진 시간과 지훈이가 해당 칸에 도착하는 시간을 비교해가며 방문 체크를 한다.
• 지훈이가 해당 칸에 도착 시 소요된 시간은 탐색 칸의 시간에 +1을 한 것과 같다.
• 테스트케이스를 여러개 통과했음에도 자꾸 틀리길래 백준 질문게시판에 올렸더니 어떤 고수분께서 10분만에 반례를 찾아주셨다... 지훈이가 특정 칸에 도착하기 전 불이 나있는 지를 체크할 때, 아예 안나있는 경우(-1)를 생각하지 못했다.

고수분께서 댓글에 남겨주신 반례

5 5

#F#J#
###.#
###.#
###.#

output : IMPOSSIBLE
answer : 4