백준 4179 - 불!

문제

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

리뷰

BFS를 활용하여 지훈이와 불의 이동을 각각 전파하는 식으로 구성하면
되는 문제였다.

지훈이와 불의 이동 순서와 관련하여 문제에서 따로 조건에 명시되어 있지
않아 지훈이가 먼저 이동을 하고 불이 전파되는 식으로 구현하였다.
문제는 같은 시간대일때 지훈이의 이동이 먼저 전파가 되고 불의 이동이
전파되어야 했는데, 해당 부분의 구현에 있어 지훈이의 경로들이 다 전파가
되지 않고 불이 전파가 되거나 하는 실수가 있어, 애를 먹었다.

우선 지훈이의 경로와 불의 경로를 별도로 저장하기 위해 jQueue 와
fQueue 를 별도로 정의하였다. bfs에서는 현재 시간을 나타내는
level 변수가 있고, jQueue와 fQueue에서 현재 시간대와 일치하는
경로만 찾아 map 에 반영해주는 식으로 로직이 진행된다.

bfs 로직의 시간복잡도는 $O(V^2)$으로 수렴하고 문제의 최대 정점 개수인
1,000에서도 시간 제한 조건인 1초를 무난하게 통과한다.

코드

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

public class Main {
    static int R, C;
    static char[][] map;
    static Queue<Node> jQueue = new ArrayDeque<>();
    static Queue<Node> fQueue = new ArrayDeque<>();


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        StringTokenizer st = new StringTokenizer(in.nextLine());
        R = parseInt(st.nextToken());
        C = parseInt(st.nextToken());

        map = new char[R][C];
        for (int y = 0; y < R; y++) {
            String line = in.nextLine();
            for (int x = 0; x < C; x++) {
                map[y][x] = line.charAt(x);

                switch (map[y][x]) {
                    case 'J':
                        jQueue.offer(new Node(x, y, 0));
                        break;
                    case 'F':
                        fQueue.offer(new Node(x, y, 0));
                        break;
                }
            }
        }

        int result = bfs();
        System.out.println(result == -1 ? "IMPOSSIBLE" : result);
        in.close();
    }

    static int bfs() {
        int[] px = {-1, 1, 0, 0};
        int[] py = {0, 0, -1, 1};

        int nx, ny;
        int level = 0;

        while (!jQueue.isEmpty()) {

            while (!jQueue.isEmpty() && jQueue.peek().level == level) {
                Node jCurrent = jQueue.poll();

                if (map[jCurrent.y][jCurrent.x] == 'F')
                    continue;


                for (int i = 0; i < px.length; i++) {
                    nx = jCurrent.x + px[i];
                    ny = jCurrent.y + py[i];

                    if (!isValid(nx, ny)) {
                        return jCurrent.level + 1;
                    }

                    if (isValid(nx, ny) && map[ny][nx] == '.') {
                        map[ny][nx] = 'J';
                        jQueue.offer(new Node(nx, ny, jCurrent.level + 1));
                    }
                }
            }

            while (!fQueue.isEmpty() && fQueue.peek().level == level) {
                Node fCurrent = fQueue.poll();

                for (int i = 0; i < px.length; i++) {
                    nx = fCurrent.x + px[i];
                    ny = fCurrent.y + py[i];

                    if (isValid(nx, ny) && (map[ny][nx] == '.' || map[ny][nx] == 'J')) {
                        map[ny][nx] = 'F';
                        fQueue.offer(new Node(nx, ny, fCurrent.level + 1));
                    }
                }
            }

            level++;
        }

        return -1;
    }

    static boolean isValid(int nx, int ny) {
        return nx >= 0 && nx < C && ny >= 0 && ny < R;
    }

    static class Node {
        int x, y, level;

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

결과