[BOJ-5427] 불(JAVA)

백준 5427 불

 

5427번: 불

 

문제 설명

 

 - 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다.

 

 - 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

 

 - 매 초마다, 불은 벽에 붙지 않으면서 동서남북 방향으로 인접한 빈 공간에 퍼져나간다.

 

 - 상근이도 동서남북 인접한 칸으로 이동할 수 있고 통과할 수 없으며, 이동시 1초가 걸린다.

 

 - 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다.

 

 - 상근이가 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

 

 - 빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하라.

 

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

 

---

 

입력 값

 

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

 

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

   ( 1 <= w, h <= 1,000 )

 

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

   '.' => 빈 공간 / '#' => 벽 / '@' => 상근이의 시작 위치 / '*' => 불

 

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

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제에서 상근이가 이동할 수 있는 경우는 벽이 아니면서 불이 붙지 않는 빈 공간이다.

 

 - 즉, 불보다 먼저 빈 공간에 간다면 이동할 수 있다는 것이다.

 

 - 해당 빈 공간에 불보다 먼저 왔는지 어떻게 판단할 수 있을까?

 

 - 간단하게 생각하면, BFS를 이용하여 알 수 있다.

탐색 알고리즘 - 너비 우선 탐색(Breadth First Search, BFS)

 

 

 - 먼저 불이 빈 공간으로 이동할 수 있는 최소 횟수를 BFS를 이용하여 구한다.

   예를 들어, #*# 와 같은 빌딩이 주어지면, 불이 이동할 수 있는 최소 횟수는 #0# 와 같다.

                 #.#                                                                              #1#

                 #.#                                                                              #2#

 

- 그 이후 상근이가 빈 공간으로 이동했을 때 불보다 먼저 이동할 수 있는지를 BFS를 이용하여 구하면 된다.

 

 - 결론적으로 정리하자면

   1. BFS를 이용하여 불이 모든 공간에 이동할 수 있는 최소 이동 횟수를 구한다.

   2. BFS를 이용하여 상근이가 모든 공간에 이동할 수 있는 최소 이동 횟수를 구한다.

      상근이는 빈 공간에 도착했을 때 불보다 빠르게 도착하여야 한다.

   3. 상근이가 모든 공간을 살펴보면서 밖으로 탈출하는 경우(빌딩 범위 밖으로 나가는 경우)에는 그 횟수를 리턴하고

      모든 경우를 살펴보더라도 탈출할 수 없다면, "IMPOSSIBLE"을 리턴한다.

 

---

 

 

소스 코드

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/5427
// 불
public class Main {

    private static int dy[]={0,0,-1,1};
    private static int dx[]={1,-1,0,0};

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int tc = Integer.parseInt(bf.readLine());

        for(int t=0;t<tc;t++){

            StringTokenizer st = new StringTokenizer(bf.readLine());

            int X = Integer.parseInt(st.nextToken());
            int Y = Integer.parseInt(st.nextToken());

            char boards[][] = new char[Y][X];
            int fire[][] = new int[Y][X];
            int visited[][] = new int[Y][X];
            Queue<Pair> q = new LinkedList<>();

            Pair startNode=null;

            for(int i=0;i<Y;i++){
                String s = bf.readLine();
                for(int j=0;j<X;j++){
                    visited[i][j]=Integer.MAX_VALUE;
                    fire[i][j]=Integer.MAX_VALUE;
                    boards[i][j]=s.charAt(j);
                    if(boards[i][j]=='*'){
                        q.add(new Pair(i,j));
                        fire[i][j]=0;
                    }

                    if(boards[i][j]=='@'){
                        startNode = new Pair(i,j);
                        visited[i][j]=0;
                    }
                }
            }

            while(!q.isEmpty()){

                Pair nowPair = q.poll();
                
                for(int d=0;d<4;d++){

                    int ny = nowPair.y+dy[d];
                    int nx = nowPair.x+dx[d];

                    int cnt = fire[nowPair.y][nowPair.x]+1;

                    if(ny < 0 || nx < 0 || ny >= Y || nx >= X || boards[ny][nx]=='#' || fire[ny][nx] <= cnt){
                        continue;
                    }

                    fire[ny][nx]=cnt;

                    q.add(new Pair(ny,nx));

                }
            }
            
            q.add(startNode);

            int result=-1;

            while (!q.isEmpty() && result==-1){

                Pair nowPair = q.poll();

                for(int d=0;d<4;d++){

                    int ny = nowPair.y+dy[d];
                    int nx = nowPair.x+dx[d];

                    int cnt = visited[nowPair.y][nowPair.x]+1;

                    if(ny < 0 || nx < 0 || ny >= Y || nx >= X ){
                        result=cnt;
                        break;
                    }

                    if(boards[ny][nx]=='#' || visited[ny][nx] <= cnt || fire[ny][nx] <= cnt){
                        continue;
                    }

                    visited[ny][nx]=cnt;

                    q.add(new Pair(ny,nx));

                }

            }
            if(result==-1){
                System.out.println("IMPOSSIBLE");
            }
            else{
                System.out.println(result);
            }
        }

    }

    static class Pair{
        int y,x;

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