백준 5427 불(Java)

문제 출처 : https://www.acmicpc.net/problem/5427

16987번: 계란으로 계란치기

문제 설명

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

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

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

입력

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

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

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

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

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

출력

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

풀이

 

코드

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

public class boj_5427 {
    static int w, h, result;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};
    static char[][] arr;
    static Queue<int[]> q;


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
            st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());
            arr = new char[h][w];
            q = new LinkedList<>();
            result = 0;

            int x = 0, y = 0;

            for (int i = 0; i < h; i++) {
                String str = br.readLine();
                for (int j = 0; j < w; j++) {
                    arr[i][j] = str.charAt(j);
                    if (arr[i][j] == '*') {
                        q.add(new int[]{i, j});
                    } else if (arr[i][j] == '@') {
                        x = i;
                        y = j;
                    }
                }
            }
            q.add(new int[]{x, y});
            sb.append(simulation() ? result : "IMPOSSIBLE").append("\n");
        }
        System.out.println(sb);
        br.close();
    }

    public static boolean simulation() {
        while (!q.isEmpty()) {
            result++;
            for (int i = 0, size = q.size(); i < size; i++) {
                int[] now = q.poll();
                for (int j = 0; j < 4; j++) {
                    int nx = now[0] + dx[j];
                    int ny = now[1] + dy[j];
                    if (nx < 0 || nx >= h || ny < 0 || ny >= w) {
                        if (arr[now[0]][now[1]] == '@') {
                            return true;
                        }
                        continue;
                    }
                    if (arr[nx][ny] != '.') {
                        continue;
                    }
                    arr[nx][ny] = arr[now[0]][now[1]];
                    q.add(new int[]{nx, ny});
                }
            }
        }

        return false;
    }
}

결과