백준 5427: 불 [Java] -포포

문제

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

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

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

입력

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

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

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

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

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

출력

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

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

5427번: 불

---

문제의 조건 중

불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 
상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

는 사실에 주목했다.

BFS를 사용한다면 상근이의 위치와 불의 위치를 큐에 넣게 될 것이다. 
그런데 상근이의 위치를 Queue에 먼저 넣는것과, 불의 위치를 Queue에 먼저 넣는것은 조금 다르다.

상근이의 위치를 Queue에 먼저 넣는다면, 상근이는 불보다 한 박자 빠르게 BFS를 실행하게 될 것이다.
이는 곧, 불이 붙을 예정인 좌표로 상근이는 아무것도 모른 채 이동하게 될 수도 있다는 뜻이다.

그럼 문제를 풀기 위해서는 불의 모든 좌표를 Queue에 먼저 넣어주어야 한다.
각각의 불들을 인접한 좌표로 옮겨 붙도록 한 뒤, 상근이의 BFS를 실행해야 할 것이다.

이외에는 다른 BFS 문제와 동일하다.

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

public class Main {
    static int n, m;
    static char[][] map;
    static StringBuilder sb;
    static Queue<Point> qu;
    static boolean[][] visit;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringTokenizer st;
        sb = new StringBuilder();

        for (int i = 0; i < t; i++) {
            qu = new LinkedList<>();
            st = new StringTokenizer(br.readLine());
            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());

            map = new char[n][m];
            visit = new boolean[n][m];

            for (int j = 0; j < n; j++) {
                String s = br.readLine();
                for (int k = 0; k < m; k++) {
                    map[j][k] = s.charAt(k);
                }
            }

            Point po = null;
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    if (map[j][k] == '*') {
                        qu.offer(new Point(j, k, 0, map[j][k]));
                        visit[j][k] = true;
                    }

                    if (map[j][k] == '@') {
                        // 불의 위치부터 큐에 넣어야 한다.
                        po = new Point(j, k, 0, map[j][k]);
                        visit[j][k] = true;
                    }
                }
            }

            qu.offer(po);
            bfs();
        }

        System.out.println(sb);
    }

    private static void bfs() {

        while (!qu.isEmpty()) {
            Point point = qu.poll();

            //만약 상근이가 맵의 테두리까지 왔다면 다음 이동 시(count+1) 탈출이 가능하다.
            if (point.value == '@' && (point.x == 0 || point.x == n-1 || point.y == 0 || point.y == m-1)) {
                sb.append(point.count + 1).append('\n');
                return;
            }

            for (int i = 0; i < 4; i++) {
                int nx = dx[i] + point.x;
                int ny = dy[i] + point.y;

                if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
                    continue;
                }
                
                // '*' 불은 벽을 제외한 모든 칸으로 번질 수 있다.
                if(point.value == '*'){
                    if (map[nx][ny] != '#' && !visit[nx][ny]) {
                        qu.offer(new Point(nx, ny, 0, '*'));
                        map[nx][ny] = '*';
                        visit[nx][ny] = true;
                    }
                }

                // '@' 상근이는 불과 벽을 제외한 모든 칸으로 이동할 수 있다.
                if (point.value == '@') {
                    if (map[nx][ny] == '#' || map[nx][ny] == '*') {
                        continue;
                    }

                    if (map[nx][ny] == '.' && !visit[nx][ny]) {
                        qu.offer(new Point(nx, ny, point.count + 1, '@'));
                        map[nx][ny] = '@';
                        visit[nx][ny] = true;
                    }
                }
            }
        }

        sb.append("IMPOSSIBLE\n");
    }

    static class Point {
        int x;
        int y;
        int count;
        char value;

        public Point(int x, int y, int count, char value) {
            this.x = x;
            this.y = y;
            this.count = count;
            this.value = value;
        }
    }
}