(백준) 불 _ 5427

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

 

🐢 설명

벽이 있는 방에서 불이나 탈출해야하는 문제이다. 이때 불은 빈공간으로만 퍼진다는 특징이 있고, 사람도 빈공간으로만 다닐 수 있다.

불이 났거나 날 공간으로는 이동할 수 없다는 조건이 있다.

방 모습이다. 이 경우 5회의 이동끝에 탈출한다.
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######

• 먼저 불이 난 좌표를 불 큐에 넣어주고 내가 존재하는 위치를 저장해 뒀다. 이후 탈출자 먼저 BFS탐색으로 이동을 하고 불에 대해 BFS 탐색 후 이동하도록 했다. 이때 큐에 담은 불이나 탈줄자의 개수만큼만 탐색을하고 번갈아 가면서 하도록 했으며 사람이 먼저 이동하고 불이 이동하도록 했다.
• 만약 사람이 이동한 곳에 불이 난다면 이동할 수 없으므로 사람에 대해서는 불의 방문체크도 하도록 했다.
• 사람 좌표에 대해서는 move 특성을 추가로 부여하여 이동을 할 때마다 move + 1을 해주었다.

 

🐢코드

//package Gold이상문제_정리;

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 불_5427 {
    static int N;
    static StringTokenizer st;
    static BufferedReader br;
    static StringBuilder answer = new StringBuilder();

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());
            escapeRoom(n, m);
        }
        System.out.print(answer);
    }

    private static void escapeRoom(int r, int c) throws IOException {
        char[][] map = new char[r][c];
        Queue<Dot> fireQ = new LinkedList<>();
        Dot me = new Dot(0, 0, 0);

        for (int i = 0; i < r; i++) {
            String line = br.readLine();
            for (int j = 0; j < c; j++) {
                map[i][j] = line.charAt(j);
                if (map[i][j] == '@') { // 탈출자
                    me = new Dot(i, j, 0);
                } else if (map[i][j] == '*') { // 불이난 모든 곳
                    fireQ.add(new Dot(i, j));
                }
            }
        }

        int start;
        if ((start = start(map, me, fireQ)) == 0) { // 이동횟수가 0인 경우 탈출 실패
            answer.append("IMPOSSIBLE").append("\n");
        } else { // 그외의 경우 탈출에 걸린 이동 횟수
            answer.append(start).append("\n");
        }
    }

    private static int start(char[][] map, Dot me, Queue<Dot> fireQ) {
        int r = map.length;
        int c = map[0].length;
        boolean[][] visited = new boolean[r][c]; // 탈출자 방문 체크
        boolean[][] fireVisited = new boolean[r][c]; // 불 방문 체크
        int[] dy = new int[]{-1, 1, 0, 0};
        int[] dx = new int[]{0, 0, -1, 1};
        Queue<Dot> meQ = new LinkedList<>();
        meQ.add(me);
        visited[me.y][me.x] = true;

        while (!meQ.isEmpty()) {

            // 나 옮기기
            int tmp = meQ.size();
            while (tmp-- > 0) { // 한턴에 움직일 수 있는 것들만 옮김
                Dot now = meQ.poll();

                if (fireVisited[now.y][now.x]) continue; // 불난 경우 이동 x

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

                    if (ny < 0 || nx < 0 || ny >= r || nx >= c) {
                        return now.move + 1; // 범위를 벗어난 경우 이동 횟수 반환
                    }
                    if (map[ny][nx] == '*') continue;
                    if (map[ny][nx] == '#') continue;
                    if (fireVisited[ny][nx]) continue; // 불난 경우 이동 x
                    if (visited[ny][nx]) continue;
                    visited[ny][nx] = true;
                    meQ.add(new Dot(ny, nx, now.move + 1));
                }
            }
            // 불 옮기기
            tmp = fireQ.size();
            while (tmp-- > 0) {
                Dot now = fireQ.poll();

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

                    if (ny < 0 || nx < 0 || ny >= r || nx >= c) continue;
                    if (fireVisited[ny][nx]) continue;
                    if (map[ny][nx] == '#') continue;
                    fireVisited[ny][nx] = true;
                    fireQ.add(new Dot(ny, nx));
                }
            }
        }
        return 0;
    }

    private static class Dot {
        int y, x;
        int move;

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

        Dot(int y, int x, int move) {
            this.y = y;
            this.x = x;
            this.move = move;
        }
    }
}

🐢 마무리