[BOJ/백준] 5427 - 불

5427번: 불

 

---

동시 탐색 BFS

---

---

• 제목

불

---

• 조건

시간 제한 :  초

메모리 제한 :  MB 

---

• 문제

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

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

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

---

• 입력

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

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

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

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

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

---

• 출력

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

---

예제 입력1	예제 출력1
3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0	2 5 IMPOSSIBLE IMPOSSIBLE IMPOSSIBLE

---

import java.io.*;
import java.util.*;

public class Main{
    static StringBuilder sb = new StringBuilder();
    static int N, M, sanggeun, minimum;
    static int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
    static char[][] arr = new char[1000][1000];
    static int[][] firetime = new int[1000][1000];
    static int[][] dist = new int[1000][1000];
    static Queue<Integer> queue = new LinkedList<Integer>();
    static void sangguenDFS(int x, int y, int time){
        if(time > minimum) return;
        for(int k = 0; k < 4; k++){
            int tx = x + dx[k];
            int ty = y + dy[k];
            if (tx < 0 || ty < 0 || tx >= N || ty >= M) {
                minimum = Math.min(minimum, time + 1);
                return;
            }
            if(arr[tx][ty] == '#') continue;
            if(arr[tx][ty] == '@') continue;
            if(firetime[tx][ty] <= time + 1) continue;
            if(time + 1 >= dist[tx][ty]) continue;
            dist[tx][ty] = time + 1;
            sangguenDFS(tx, ty, time + 1);
        }
    }
    static void fireBFS(){
        while(!queue.isEmpty()){
            int p = queue.poll();
            int x = p / M;
            int y = p % M;
            for(int k = 0; k < 4; k++){
                int tx = x + dx[k];
                int ty = y + dy[k];
                if(tx < 0 || ty < 0 || tx >= N || ty >= M) continue;
                if(firetime[tx][ty] <= firetime[x][y] + 1) continue;
                if(arr[tx][ty] == '#') continue;
                if(arr[tx][ty] == '@') continue;
                firetime[tx][ty] = firetime[x][y] + 1;
                queue.add(tx * M + ty);
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        for(int t = 0; t < T; t++){
            minimum = Integer.MAX_VALUE;
            st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            for(int i = 0; i < N; i++){
                String temp = br.readLine();
                for(int j = 0; j < M; j++){
                    arr[i][j] = temp.charAt(j);
                    dist[i][j] = Integer.MAX_VALUE;
                    firetime[i][j] = Integer.MAX_VALUE;
                    if(arr[i][j] == '*') {
                        firetime[i][j] = 0;
                        queue.add(i * M + j);
                    }
                    if(arr[i][j] == '@') sanggeun = i * M + j;
                }
            }

            fireBFS();

            dist[sanggeun / M][sanggeun % M] = 0;
            sangguenDFS(sanggeun / M, sanggeun % M, 0);
            sb.append(minimum == Integer.MAX_VALUE ? "IMPOSSIBLE" : minimum).append("\n");
        }
        System.out.print(sb);
    }
}