문제

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

문제

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

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

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

입력

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

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

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

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

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

출력

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

풀이

BFS로 풀 수 있는 문제였다.

1. 배열을 벽, 불, 상근이, 빈 공간 으로 나눠서 값을 업데이트 해준다.
2. 움직일 수 있는 사람이 있는지 확인
3. 현재 시점에 불들을 4 방향으로 불을 퍼뜨린다 (시간이 없을 경우 한번에 불 다붙이고 끝나버림)
4. 현재 시점에 사람을 4 방향으로 이동시킨다.
5. 만약 사람이 배열의 끝 부분에 도착했다면 가장 빨리 도착한 경우 업데이트 해준다.

푸는데 중요했던 부분은 두가지가 있었다.

불이 2개가 붙어있다면, 주기마다 2개의 불을 다 이동시켜야 하는 것

빌딩을 탈출하는데에 가장 빠른 시간을 출력하는 것

package com.company.baekjoon;

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

public class B5427 {
    static final int WALL = -2;
    static final int FIRE = -1;
    static final int EMPTY_SPACE = 0;
    static final int PERSON = 1;

    static int[] dx = new int[] {-1,1,0,0};
    static int[] dy = new int[] {0,0,-1,1};
    static int[][] graph;
    static Queue<int[]> fires = new LinkedList<>();
    static Queue<int[]> person = new LinkedList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            String[] size = br.readLine().split(" ");
            int w = Integer.parseInt(size[0]);
            int h = Integer.parseInt(size[1]);
            graph = new int[h][w];
            fires.clear();
            person.clear();
            int answer = Integer.MAX_VALUE;
            int time = 0;
            for (int j = 0; j < h; j++) {
                char[] s = br.readLine().toCharArray();
                for (int k = 0; k < s.length; k++) {
                    if (s[k] == '#') {
                        graph[j][k] = WALL;
                    } else if (s[k] == '.') {
                        graph[j][k] = EMPTY_SPACE;
                    } else if (s[k] == '*') {
                        graph[j][k] = FIRE;
                        fires.add(new int[] {j,k,0});
                    } else {
                        graph[j][k] = PERSON;
                        person.add(new int[]{j,k,0});
                    }
                }
            }
            // 불 먼저 움직이고 사람 움직이기
            while (!person.isEmpty()) {
                while (fires.peek() != null && fires.peek()[2] == time ) {
                    int[] fire = fires.poll();
                    for (int j = 0; j < dx.length; j++) {
                        int cy = fire[0] + dy[j];
                        int cx = fire[1] + dx[j];

                        if (cx < 0 || cy < 0 || cx >= w || cy >= h) continue;
                        if (graph[cy][cx] == FIRE) continue;
                        if (graph[cy][cx] != WALL) {
                            graph[cy][cx] = FIRE;
                            fires.add(new int[]{cy, cx, fire[2] + 1});
                        }
                    }
                }

                while (person.peek() != null && person.peek()[2] == time) {
                    int[] p = person.poll();
                    for (int j = 0; j < dx.length; j++) {
                        int cy = p[0] + dy[j];
                        int cx = p[1] + dx[j];

                        if (cx < 0 || cy < 0 || cx >= w || cy >= h) {
                            answer = Math.min(answer,p[2]);
                            break;
                        }
                        if (graph[cy][cx] == EMPTY_SPACE) {
                            graph[cy][cx] = PERSON;
                            person.add(new int[]{cy, cx, p[2] + 1});
                        }
                    }
                }
                time++;
            }
            if (answer == Integer.MAX_VALUE)
                sb.append("IMPOSSIBLE").append("\n");
            else
                sb.append(answer+1).append("\n");
        }
        System.out.println(sb);
    }
}