BOJ_4179 : 불!

👉 문제링크

---

---

🔸 문제 분석 🔸

• R x C 격자판에서 지훈이의 위치와 불들의 위치가 주어진다.
• 지훈이는 1분에 상하좌우 4방향으로 이동할 수 있고, 불도 1분에 4방향으로 확산된다.
• 격자판의 가장자리로 가면 미로를 탈출 할 수 있다.
• 지훈이가 불을 피해 미로를 탈출하기 위한 최단시간을 출력한다.
  만약 탈출하지 못한다면 "IMPOSSIBLE"을 출력한다.

🔸 문제 풀이 🔸

• 격자판에서 최단 거리를 구하는 단순 BFS 문제이다. 하지만 지훈이의 이동과 불의 확산 모두 고려해야 한다.
  • 큐를 이용한 BFS 구현에서 큐 사이즈만큼 반복해서 '1분'의 움직임을 제한해야 한다.
• 지훈이의 위치는 맵에 그리지 않고 큐에만 넣고, 불은 맵에 'F'로 표시해 간다.
  • 지훈이는 불로 이동할 수 없을 뿐만 아니라, 큐에서 꺼냈을 때 현재 위치가 'F'로 되어있으면 불에 집어삼켜진 것이므로 다음 원소를 확인한다.
• 지훈이가 가장자리로 이동했다면 바로 정답을 반환하고, 만약 큐가 비어질 때 까지 탈출하지 못했다면 0을 반환해서 "IMPOSSIBLE"을 출력한다.

🔸 코드 🔸

import java.io.*;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static final int[] dx = {-1, 0, 1, 0};
    private static final int[] dy = {0, 1, 0, -1};
    private static int R, C;
    private static char[][] map;
    private static Queue<Point> run, burn;

    public static void main(String[] args) throws IOException {
        // Input
        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());
        map = new char[R][C];

        run = new ArrayDeque<>();
        burn = new ArrayDeque<>();

        for (int i = 0; i < R; i++) {
            char[] chars = br.readLine().toCharArray();
            for (int j = 0; j < C; j++) {
                if (chars[j] == 'J') {
                    run.add(new Point(i, j));
                    map[i][j] = '.';
                } else if (chars[j] == 'F') {
                    burn.add(new Point(i, j));
                    map[i][j] = 'F';
                } else
                    map[i][j] = chars[j];
            }
        }

        // BFS
        int result = escape();

        // Output
        if (result == 0)
            bw.write("IMPOSSIBLE");
        else
            bw.write(Integer.toString(result));
        bw.flush();
    }

    private static int escape() {
        boolean[][] visited = new boolean[R][C];
        visited[run.peek().row][run.peek().col] = true;

        int cnt = 0;

        while (!run.isEmpty()) {
            int size = run.size();

            // 지훈 이동
            for (int i = 0; i < size; i++) {
                Point jihun = run.poll();

                if (map[jihun.row][jihun.col] == 'F') {
                    continue;
                }

                for (int j = 0; j < 4; j++) {
                    int row = jihun.row + dx[j];
                    int col = jihun.col + dy[j];
                    if (0 > row || row >= R || 0 > col || col >= C) {
                        return cnt + 1;
                    }
                    if (!visited[row][col] && map[row][col] == '.') {
                        visited[row][col] = true;
                        run.add(new Point(row, col));
                    }
                }
            }
            cnt++;

            // 불 번짐
            size = burn.size();
            for (int i = 0; i < size; i++) {
                Point fire = burn.poll();
                for (int j = 0; j < 4; j++) {
                    int row = fire.row + dx[j];
                    int col = fire.col + dy[j];
                    if (0 <= row && row < R && 0 <= col && col < C && map[row][col] == '.') {
                        map[row][col] = 'F';
                        burn.add(new Point(row, col));
                    }
                }
            }
        }
        return 0;
    }

    private static class Point {
        int row, col;

        public Point(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}

🔸 코드 해석 🔸

• char형 2차원 배열로 맵 정보를 입력받고, 지훈이의 시작 위치는 좌표만 큐에 담고 '.'으로 기록한다.
  • 불의 시작 위치도 큐에 담지만, 맵에는 'F'를 기록한다.
• BFS탐색은 escape() 메서드에서 진행한다.
  • 1분의 시간 흐름을 cnt에 누적해서 기록하고, 지훈이가 탈출했을 시 cnt를 반환한다.
  • 지훈이 위치 큐의 모든 원소를 확인했을 때에도 탈출하지 못했다면 0을 반환한다.
• 반환값에 따라 최소 시간 혹은 "IMPOSSIBLE"을 출력한다.

---

🔸 end 🔸

• 알고리즘 자체는 BFS로 간단했지만, 시작 할 때 불의 위치가 여러개일 수 있다는 점을 놓치고 틀렸다.
  • 더욱 문제를 자세히 읽을 필요가 있다... 다음 문제에서는 제출 전에 테스트 케이스도 많이 만들고, 한 번에 맞추는걸 목표로 해야겠다.