[백준] 5427 불 [java]

문제

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

DFS vs BFS

문제에서, 몇 초만에 탈출하는지, 최소 시간을 구해야 하기 때문에, 직관적으로 보면 DFS를 사용하는게 편하다. 왜냐면, DFS는 깊이 우선 탐색으로, 깊이를 측정하면서 탐색하기에 적합하기 때문이다.
하지만, DFS는 최악의 상황에 성능이 좋지 않고, BFS가 평균적으로 DFS보다 성능이 좋기 때문에, BFS를 사용하였다. 그러면 BFS로 탐색의 레벨을 어떻게 측정할까?

너비우선 탐색으로 현재 탐색 레벨 측정하기

public static void fireSpread(Queue<Pos> firePos){

        int currTurnSize = firePos.size();

        while(currTurnSize-- > 0){

            Pos pos = firePos.poll();

            for(int i = 0; i < 4; i++){
                int nextX = pos.x + dirX[i];
                int nextY = pos.y + dirY[i];

                if(isInRange(nextX, nextY) && (!alreadyFired[nextY][nextX] && map[nextY][nextX] != '#')){
                    alreadyFired[nextY][nextX] = true;
                    map[nextY][nextX] = '*';
                    firePos.add(new Pos(nextX, nextY));
                }
            }
        }
    }

위 코드는 한 단계마다 불이 퍼지는 함수이다.
큐를 사용하여 처음에 현재 큐의 사이즈를 저장해놓고, 그 사이즈만큼만 뽑아서 탐색하면, 해당 레벨만큼만 탐색할 수 있다.

위 사진에서 처음에 1 위치에서 시작한다 하면, 처음 size는 1이다. 1을 뽑아내고 1에서 불이 번질 수 있는 2, 3을 큐에 넣는다. 그러면 이제 size는 0이 되고 한 레벨이 끝난다. (현재 레벨 : 1)
다음 레벨로 이동하여 size가 2가 되었다.
2를 뽑아내면 2에서 불이 번질 수 있는 4를 큐에 넣는다. 그러면 size는 1이 된다.
3을 뽑아내고 3에서 불이 번질 수 있는 5를 큐에 넣는다. 그러면 size는 0이 되어 이번 레벨이 끝난다.
(현재 레벨 : 2)
다음 레벨로 이동하여 size가 2가 되었다.

..반복한다..

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// 불이 동서남북으로 번짐. 불이 붙었거나, 다음에 붙을 칸을 못감. 최대한 빨리 탈출하는 시간
public class Main {

    public static class Pos{
        int x, y;
        Pos(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    public static int[] dirX = {0, 1, 0, -1};
    public static int[] dirY = {-1, 0, 1, 0};
    public static int row, col;
    public static char[][] map;
    public static boolean[][] alreadyFired;

    public static boolean isInRange(int currX, int currY){
        if((currX >= 0 && currX < col) &&(currY >= 0 && currY < row)) return true;
        else return false;
    }

    public static void fireSpread(Queue<Pos> firePos){

        int currTurnSize = firePos.size();

        while(currTurnSize-- > 0){

            Pos pos = firePos.poll();

            for(int i = 0; i < 4; i++){
                int nextX = pos.x + dirX[i];
                int nextY = pos.y + dirY[i];

                if(isInRange(nextX, nextY) && (!alreadyFired[nextY][nextX] && map[nextY][nextX] != '#')){
                    alreadyFired[nextY][nextX] = true;
                    map[nextY][nextX] = '*';
                    firePos.add(new Pos(nextX, nextY));
                }
            }
        }
    }

    public static int BFS(Queue<Pos> queue, int currCnt, boolean[][] check){

        int currTurnSize = queue.size();        //이번 턴에 확인할 위치

        boolean isEnd = true;
        while(currTurnSize-- > 0) {

            Pos currPos = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nextX = currPos.x + dirX[i];
                int nextY = currPos.y + dirY[i];

                if(isInRange(nextX, nextY)) {
                    if (!check[nextY][nextX] && map[nextY][nextX] == '.') {
                        check[nextY][nextX] = true;
                        queue.add(new Pos(nextX, nextY));
                        isEnd = false;
                    }
                }
                else{
                    queue.clear();
                    return currCnt + 1;
                }
            }
        }

        if(isEnd) return -1;

        return currCnt + 1;
    }

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

        while(tCase-- > 0){
            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            col = Integer.parseInt(stringTokenizer.nextToken());
            row = Integer.parseInt(stringTokenizer.nextToken());

            map = new char[row][col];
            alreadyFired = new boolean[row][col];
            int startX = 0, startY = 0;                 // 상근 시작 위치
            Queue<Pos> firePos = new LinkedList<>();

            for(int i = 0; i < row; i++){
                String str = bufferedReader.readLine();
                for(int j = 0; j < col; j++){
                    map[i][j] = str.charAt(j);
                    if(map[i][j] == '@'){
                        startX = j;
                        startY = i;
                        map[i][j] = '.';
                    }
                    else if(map[i][j] == '*'){
                        alreadyFired[i][j] = true;
                        firePos.add(new Pos(j, i));
                    }
                }
            }
            boolean[][] check = new boolean[row][col];

            Queue<Pos> queue = new LinkedList<>();
            queue.add(new Pos(startX, startY));

            int cnt = 0;
            while(!queue.isEmpty()){

                fireSpread(firePos);

                cnt = BFS(queue, cnt, check);
            }

            if(cnt == -1) System.out.println("IMPOSSIBLE");
            else System.out.println(cnt);

        }
    }
}