[BOJ] 5427: 불 (JAVA)

문제

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

 

여담

테스트 케이스마다 큐를 초기화하지 않아서 틀렸었다. 이런 실수가 진짜 치명적인건데....ㅎ 맞는 것 같은데 틀리면 제일 먼저 초기화와 변수를 확인하자.. 

 

풀이

빌딩을 탈출할 수 있는 최소 시간을 구하는 것이므로, BFS 탐색을 이용하면 된다.

 

1초마다 불이 퍼지고 상근이가 이동하며, 상근이는 불이 퍼진 곳이나 퍼질 곳으로 이동할 수 없다. 따라서 불을 먼저 퍼뜨린 후, 상근이를 이동시키는 방법을 반복하면 된다.

 

이때, 불이 더 이상 퍼질 수 없더라도 상근이가 탈출을 하는 데에는 아무 상관이 없다. 따라서 상근이가 더 이상 움직일 수 없을 경우(= 큐가 빈 경우)에만 BFS 탐색을 종료하면 된다.

 

자세한 내용은 코드를 참고하면 된다.

 

코드

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

public class Main {
    static int w, h;
    static char[][] map;
    static boolean[][] visited;
    static Queue<int[]> fireQueue, sgQueue;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());
            map = new char[h][w];
            visited = new boolean[h][w];
            fireQueue = new LinkedList<>();
            sgQueue = new LinkedList<>();
            for (int i = 0; i < h; i++) {
                String line = br.readLine();
                for (int j = 0; j < w; j++) {
                    map[i][j] = line.charAt(j);
                    if (map[i][j] == '*') { // 불의 시작 위치 저장하기
                        fireQueue.offer(new int[]{i, j});
                        visited[i][j] = true;
                    } else if (map[i][j] == '@') { // 상근이의 초기 위치 저장하기
                        sgQueue.offer(new int[]{i, j});
                        visited[i][j] = true;
                    }
                }
            }
            int bfs = bfs();
            sb.append(bfs == -1 ? "IMPOSSIBLE" : bfs).append("\n");
        }
        System.out.println(sb.toString());
    }

    static int bfs() {
        int time = 0;
        int[][] move = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!sgQueue.isEmpty()) { // 상근이가 더 이상 이동할 수 없는 경우 종료
            time++;

            // 불 먼저 이동하기
            int size = fireQueue.size();
            for (int i = 0; i < size; i++) {
                int[] now = fireQueue.poll();

                for (int j = 0; j < 4; j++) {
                    int nx = now[0] + move[j][0];
                    int ny = now[1] + move[j][1];
                    if (nx < 0 || ny < 0 || nx >= h || ny >= w || visited[nx][ny]) {
                        continue;
                    }

                    if (map[nx][ny] != '#') { // 불은 벽을 제외하고 모두 번질 수 있음
                        fireQueue.offer(new int[]{nx, ny});
                        visited[nx][ny] = true;
                    }
                }
            }
            // 상근이 이동하기
            size = sgQueue.size();
            for (int i = 0; i < size; i++) {
                int[] now = sgQueue.poll();
                int x = now[0], y = now[1];

                for (int j = 0; j < 4; j++) {
                    int nx = x + move[j][0];
                    int ny = y + move[j][1];
                    if (nx < 0 || ny < 0 || nx >= h || ny >= w) { // 지도 범위를 벗어나면 탈출한 것
                        return time;
                    }

                    // 방문하지 않았거나 불이 붙지 않았고 빈 공간인 경우 이동 가능
                    if (!visited[nx][ny] && map[nx][ny] == '.') {
                        sgQueue.offer(new int[]{nx, ny});
                        visited[nx][ny] = true;
                    }
                }
            }
        }
        return -1;
    }
}

---