[백준] 불 - Java

문제 출처

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

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

예제 입력 1 복사

5
4 3
####
#*@.
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
7 4
###.###
#....*#
#@....#
.######
5 5
.....
.***.
.*@*.
.***.
.....
3 3
###
#@#
###

풀이 방법

• BFS를 두개 활용(불 번질 때, 상근이가 이동 할 때)하면 되는 문제였다.
  • 초기에, 불 번짐은 완탐으로 해도되지 않을까 했으나 테스트 케이스가 최대 100개, 배열의 크기가 최대 1,000,000인 것을 고려하지 못하고... 시간초과가 났다.
• 따라서 각각을 큐를 이용해 1번 씩 불번짐 또는 이동을 해주었고, 상근이가 가장자리에 도착하게되면 숫자를, 그 전에 이동 경로가 차단된다면 IMPOSSIBLE을 출력해주었다.

예외 사항

• move 메서드에 보면 dq.clear가 있는데, dq.clear()를 하지 않고 return을 해두면 메서드 밑은 실행이 되지 않겠으나 dq 내부에 요소는 남아있어 while문을 탈출하지 못하게 되므로 주의!!

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    static int tc, w, h, sr, sc;
    static char[][] building;
    static boolean isExit;
    static boolean[][] check;
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tc = Integer.parseInt(br.readLine());

        for (int t = 0; t < tc; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

            building = new char[h][w];
            check = new boolean[h][w];
            isExit = false;
            Deque<int[]> fq = new ArrayDeque<>();

            for (int i = 0; i < h; i++) {
                String str = br.readLine();
                for (int j = 0; j < w; j++) {
                    building[i][j] = str.charAt(j);
                    if (building[i][j] == '@') {
                        sr = i;
                        sc = j;
                    }
                    if( building[i][j] == '*'){
                        fq.add(new int[]{i, j});
                    }
                }
            }

            Deque<Point> dq = new ArrayDeque<>();
            dq.add(new Point(sr, sc, 0));
            check[sr][sc] = true;

            while (!dq.isEmpty()) {
                // 불이 먼저 번짐
                fire(fq);
                // 상근이 이동
                move(dq);
            }
            if (!isExit) {
                System.out.println("IMPOSSIBLE");
            }
        }
    }

    public static void fire(Deque<int[]> fq) {
        int fqSize = fq.size();
        for(int i = 0; i < fqSize; i++){
            int[] cur = fq.poll();
            for(int d = 0; d < 4; d++){
                int nr = cur[0] + dr[d];
                int nc = cur[1] + dc[d];

                if(checkArea(nr, nc) && building[nr][nc] == '.'){
                    building[nr][nc] = '*';
                    fq.add(new int[]{nr, nc});
                }
            }
        }
    }

    public static boolean checkArea(int nr, int nc) {
        if (nr >= 0 && nr < h && nc >= 0 && nc < w) {
            return true;
        }
        return false;
    }

    public static class Point {
        int r;
        int c;
        int time;

        public Point(int r, int c, int time) {
            this.r = r;
            this.c = c;
            this.time = time;
        }

    }

    public static void move(Deque<Point> dq){
        int dqSize = dq.size();

        for (int i = 0; i < dqSize; i++) {
            Point cur = dq.poll();

            // 탈출 가능 시
            if (cur.r == 0 || cur.r == h - 1 || cur.c == 0 || cur.c == w - 1) {
                isExit = true;
                System.out.println(cur.time + 1);
                dq.clear();
                return;
            }

            for (int d = 0; d < 4; d++) {
                int nr = cur.r + dr[d];
                int nc = cur.c + dc[d];

                // 범위 내 & 방문 X & 빈 공간인경우
                if (checkArea(nr, nc) && !check[nr][nc] && building[nr][nc] == '.') {
                    check[nr][nc] = true;
                    dq.add(new Point(nr, nc, cur.time + 1));
                }
            }
        }
    }
}

결과

회고

• 그래도 해본 BFS라 쉬울줄 알았는데..!