백준 4179 불! (Java)

1. 문제

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

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

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

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

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

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

입력

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

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

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

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

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

출력

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

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

 

2. 풀이

해당 문제에서는 지훈이도 이동하고, 불도 이동한다. 지훈이를 먼저 이동시키고 불이 번지면 불이 닿을 위치에 지훈이가 이동하게 되므로 불길이 닿는 시간을 먼저 계산하고, 그 범위 내에서 지훈이를 이동시키도록 하자.

        for (int i = 0; i < r; i++) {
            Arrays.fill(fireMap[i], -1);
            Arrays.fill(jMap[i], -1);
        }

        for (int i = 0; i < r; i++) {
            String input = reader.readLine();
            for (int j = 0; j < c; j++) {
                if (input.charAt(j) == 'F') {
                    fireMap[i][j] = 0;
                    fq.offer(new Node(i, j));
                } else if (input.charAt(j) == 'J') {

                    if (i == 0 || i == r - 1 || j == 0 || j == c - 1) {
                        System.out.println(1);
                        return;
                    }

                    jMap[i][j] = 0;
                    jq.offer(new Node(i, j));
                }

                map[i][j] = input.charAt(j);

            }
        }

입력은 이렇게 받는다. 불과 지훈이에 대해 아직 방문하지 않았다면 -1, 방문했다면 그 시간을 나타내는 배열을 초기화하고, 미로의 구성을 따로 입력받는다.

 //불에 대한 bfs
        while (!fq.isEmpty()) {
            Node cur = fq.poll();

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

                //배열을 벗어나는 지 확인                     //벽이 아니고 아직 방문하지 않았다면
                if (isNotRange(ny, nx) || map[ny][nx] == '#' || fireMap[ny][nx] != -1) continue;


                fq.offer(new Node(ny, nx));
                fireMap[ny][nx] = fireMap[cur.y][cur.x] + 1;

            }

        }

우선 불에 대해 bfs를 돌린다. 불은 매 시간마다 사방으로 번지며, 벽이 있는 경우 번질 수 없다. 이 조건에 따라 탐색을 한다.

 

while (!jq.isEmpty()) {
            Node cur = jq.poll();

            if (cur.y == 0 || cur.y == r - 1 || cur.x == 0 || cur.x == c - 1) {
                System.out.println(jMap[cur.y][cur.x] + 1);
                return;
            }

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

                //배열을 벗어나는 지 확인
                if (isNotRange(ny, nx) || map[ny][nx] == '#'
                        || (fireMap[ny][nx] != -1 && fireMap[ny][nx] <= jMap[cur.y][cur.x] + 1)
                        || jMap[ny][nx] != -1) {
                    continue;
                }


                jq.offer(new Node(ny, nx));
                jMap[ny][nx] = jMap[cur.y][cur.x] + 1;


            }
        }

지훈이에 대해 bfs를 돌린다. 해당 위치가 모서리면 탈출하고, 그렇지 않다면 사방에 대해 미로 크기, 벽 및 방문 여부를 확인하고, 불길이 닿는 시간보다 더 빨리 도착했는 지 확인 후 이동한다.

 

탐색을 모두 했음에도 탈출하지 못했다면 IMPOSSIBLE을 출력한다. 

 

3. 코드 전문

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static char[][] map;

    static int[][] fireMap;
    static int[][] jMap;

    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};

    static int r;
    static int c;

    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        r = Integer.parseInt(tokenizer.nextToken());
        c = Integer.parseInt(tokenizer.nextToken());

        map = new char[r][c];
        fireMap = new int[r][c];
        jMap = new int[r][c];

        Queue<Node> jq = new ArrayDeque<>();
        Queue<Node> fq = new ArrayDeque<>();

        for (int i = 0; i < r; i++) {
            Arrays.fill(fireMap[i], -1);
            Arrays.fill(jMap[i], -1);
        }

        for (int i = 0; i < r; i++) {
            String input = reader.readLine();
            for (int j = 0; j < c; j++) {
                if (input.charAt(j) == 'F') {
                    fireMap[i][j] = 0;
                    fq.offer(new Node(i, j));
                } else if (input.charAt(j) == 'J') {

                    if (i == 0 || i == r - 1 || j == 0 || j == c - 1) {
                        System.out.println(1);
                        return;
                    }

                    jMap[i][j] = 0;
                    jq.offer(new Node(i, j));
                }

                map[i][j] = input.charAt(j);

            }
        }


        //불에 대한 bfs
        while (!fq.isEmpty()) {
            Node cur = fq.poll();

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

                //배열을 벗어나는 지 확인                     //벽이 아니고 아직 방문하지 않았다면
                if (isNotRange(ny, nx) || map[ny][nx] == '#' || fireMap[ny][nx] != -1) continue;


                fq.offer(new Node(ny, nx));
                fireMap[ny][nx] = fireMap[cur.y][cur.x] + 1;

            }

        }


        while (!jq.isEmpty()) {
            Node cur = jq.poll();

            if (cur.y == 0 || cur.y == r - 1 || cur.x == 0 || cur.x == c - 1) {
                System.out.println(jMap[cur.y][cur.x] + 1);
                return;
            }

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

                //배열을 벗어나는 지 확인
                if (isNotRange(ny, nx) || map[ny][nx] == '#'
                        || (fireMap[ny][nx] != -1 && fireMap[ny][nx] <= jMap[cur.y][cur.x] + 1)
                        || jMap[ny][nx] != -1) {
                    continue;
                }


                jq.offer(new Node(ny, nx));
                jMap[ny][nx] = jMap[cur.y][cur.x] + 1;


            }
        }


        System.out.println("IMPOSSIBLE");


    }

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

class Node {
    int y;
    int x;

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