[BOJ] 5427. 불 - BFS

[BOJ] 5427. 불 - BFS

제출일 : 2019-09-04

문제 풀이 시간 : 1H 15M

난이도 : ★★★

Problem

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

Input

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

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

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

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

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

Output

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

Example

input

5
4 3
####
#*@.
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
7 4
###.###
#....*#
#@....#
.######
5 5
.....
.***.
.*@*.
.***.
.....
3 3
###
#@#
###

output

2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE

Solution & Inpression

BFS 응용 문제.불이 먼저 퍼지고 사람이 이동. 한턴 한턴 수행하면 쉽게 풀리는 문제였지만 처음부터 생각하기 힘들었던 문제.

Code

언어 : JAVA

메모리 : 119,172 kb

실행시간 : 720 ms

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

public class Main {
    static class pos {
        int y;
        int x;

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

    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("res/백준_5427_불.txt"));
        int dy[] = { -1, 1, 0, 0 };
        int dx[] = { 0, 0, 1, -1 };
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        Queue<pos> fire = new LinkedList<>();
        Queue<pos> me = new LinkedList<>();
        for (int tc = 1; tc <= T; tc++) {
            me.clear();
            fire.clear();
            boolean flag = false;
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            char[][] map = new char[h][w];
            boolean[][] visit = new boolean[h][w];
            int py = 0, px = 0, flame = 0, per = 0;
            for (int y = 0; y < h; y++) {
                map[y] = br.readLine().toCharArray();
                for (int x = 0; x < w; x++) {
                    if (map[y][x] == '*') {
                        fire.offer(new pos(y, x));
                    } else if (map[y][x] == '@') {
                        visit[y][x] = true;
                        me.offer(new pos(y, x));
                        map[y][x] = '.';
                    }
                }
            }
            int result = 0;
            while (!me.isEmpty()) {
                result++;
                flame = fire.size();
                for (int f = 0; f < flame; f++) {// 불을 먼저 붙여버리겠음
                    int y = fire.peek().y;
                    int x = fire.peek().x;
                    fire.poll();
                    for (int i = 0; i < 4; i++) {
                        int ny = y + dy[i];
                        int nx = x + dx[i];
                        if (ny >= 0 && nx >= 0 && ny < h && nx < w && map[ny][nx] == '.') {
                            map[ny][nx] = '*';
                            fire.offer(new pos(ny, nx));
                        }
                    }
                }

                per = me.size();
                for (int pidx = 0; pidx < per; pidx++) {
                    py = me.peek().y;
                    px = me.peek().x;
                    me.poll();
                    if ((py == 0 || px == 0 || py == h - 1 || px == w - 1)) { // 다음번에 바로간다
                        flag = true;
                        me.clear();
                        break;
                    }
                    for (int i = 0; i < 4; i++) {
                        int npy = py + dy[i];
                        int npx = px + dx[i];
                        if (npy >= 0 && npx >= 0 && npy < h && npx < w && map[npy][npx] == '.' && !visit[npy][npx]) {
                            me.offer(new pos(npy, npx));
                            visit[npy][npx] = true;
                        }
                    }
                }
            }
            if (flag)
                System.out.println(result);
            else
                System.out.println("IMPOSSIBLE");
        }
    }
}