[백준] 4179. 불!

문제 링크

[백준] 4179. 불!

풀이 과정

static char[][] map;
static int[][] fire;
static boolean[][] visit;

사용되는 2차원 배열들은 위와 같습니다.

• map : 문제의 입력을 받기 위해 사용.
• fire : 해당 좌표에 불이 도달하는 시간.
• visit : 지훈이가 맵의 가장자리로 이동하는 BFS 탐색에 이용되는 방문 배열.

for (int i = 0; i < R; i++) Arrays.fill(fire[i], MAX);

불을 번지게 하여 같은 좌표에 더 적은 시간으로 불이 도달하면 갱신해주기 위해 fire 배열을 맥시멈 값으로 초기화해줍니다.

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

    if (ch == 'J') J = new int[]{i, j};
    else if (ch == 'F') {
        F.add(new int[]{i, j});
        fire[i][j] = 0;
    }
}

불의 좌표는 리스트 F에 모두 담아두고, 해당 좌표에는 0초에 도달한다는 표시를 해둡니다.

Queue<Point> queue = new LinkedList<>();
for (int[] f : F) queue.add(new Point(f[0], f[1], 0));

while (!queue.isEmpty()) {
    Point now = queue.poll();

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

        if (!inRange(nx, ny) || now.time + 1 >= fire[nx][ny] || map[nx][ny] == '#') continue;

        fire[nx][ny] = now.time + 1;
        queue.add(new Point(nx, ny, now.time + 1));
    }
}

큐를 이용하여 불을 번지도록 합니다. 상하좌우 방면으로, 해당 좌표까지 더 적은 시간으로 도달할 수 있다면 갱신해줍니다.

visit[J[0]][J[1]] = true;
queue.add(new Point(J[0], J[1], 0));

while (!queue.isEmpty()) {
    Point now = queue.poll();

    if (now.x == 0 || now.x == R - 1 || now.y == 0 || now.y == C - 1) {
        answer = now.time + 1;
        break;
    }

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

        if (!inRange(nx, ny) || visit[nx][ny] || map[nx][ny] == '#' || now.time + 1 >= fire[nx][ny]) continue;

        visit[nx][ny] = true;
        queue.add(new Point(nx, ny, now.time + 1));
    }
}

모든 좌표에 대해 불이 번지는 데에 필요한 시간을 미리 구해놨다면, 지훈(J)이의 좌표를 시작으로 가장자리로 가는 BFS 탐색을 시작합니다. 다음 좌표까지 가는데 걸린 시간이 불이 번진 시간보다 적다면 갈 수 있다고 판단합니다.

코드

import java.util.*;

public class Main {
    static int R, C;
    static char[][] map;
    static int[][] fire;
    static boolean[][] visit;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int[] J;
    static ArrayList<int[]> F;
    static final int MAX = 987654321;
    static int answer = MAX;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        R = sc.nextInt();
        C = sc.nextInt();
        map = new char[R][C];
        fire = new int[R][C];
        visit = new boolean[R][C];
        F = new ArrayList<>();

        for (int i = 0; i < R; i++) Arrays.fill(fire[i], MAX);

        for (int i = 0; i < R; i++) {
            String s = sc.next();

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

                if (ch == 'J') J = new int[]{i, j};
                else if (ch == 'F') {
                    F.add(new int[]{i, j});
                    fire[i][j] = 0;
                }
            }
        }

        Queue<Point> queue = new LinkedList<>();
        for (int[] f : F) queue.add(new Point(f[0], f[1], 0));

        while (!queue.isEmpty()) {
            Point now = queue.poll();

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

                if (!inRange(nx, ny) || now.time + 1 >= fire[nx][ny] || map[nx][ny] == '#') continue;

                fire[nx][ny] = now.time + 1;
                queue.add(new Point(nx, ny, now.time + 1));
            }
        }

        visit[J[0]][J[1]] = true;
        queue.add(new Point(J[0], J[1], 0));

        while (!queue.isEmpty()) {
            Point now = queue.poll();

            if (now.x == 0 || now.x == R - 1 || now.y == 0 || now.y == C - 1) {
                answer = now.time + 1;
                break;
            }

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

                if (!inRange(nx, ny) || visit[nx][ny] || map[nx][ny] == '#' || now.time + 1 >= fire[nx][ny]) continue;

                visit[nx][ny] = true;
                queue.add(new Point(nx, ny, now.time + 1));
            }
        }

        System.out.println(answer == MAX ? "IMPOSSIBLE" : answer);
    }

    static boolean inRange(int x, int y) {
        if (x < 0 || x > R - 1 || y < 0 || y > C - 1) return false;
        return true;
    }

    static class Point {
        int x, y, time;

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