[백준 Gold 4] 5427 불 - Java

문제링크 : https://www.acmicpc.net/problem/5427

5427번: 불

 

접근 과정 : 

• 단순하게 BFS를 이용한 시뮬레이션이라고 생각했다.
• 각 테스트 케이스마다 BFS를 이용해서 탈출이 가능한지 시뮬레이션했다.
• 다만, 다음에 불이 번질 칸으로 이동하지 못하므로 불을 먼저 이동시키고 상근이가 가능한 경로를 탐색했다.

 

소스 코드 및 결과 :

package BOJ;

/* 
    불
*/

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

public class BOJ5427 {

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        int[][] move = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());

            char[][] map = new char[h][w];
            Queue<int[]> point = new LinkedList<>();
            Queue<int[]> fire = new LinkedList<>();

            for (int i = 0; i < h; i++) {
                map[i] = br.readLine().toCharArray();
                for (int j = 0; j < w; j++) {
                    if (map[i][j] == '@') {
                        point.add(new int[] { i, j });
                        map[i][j] = '.';
                    } else if (map[i][j] == '*') {
                        fire.add(new int[] { i, j });
                    }
                }
            }

            int count = 0;
            boolean escape = false;
            boolean[][] visit = new boolean[h][w];
            visit[point.peek()[0]][point.peek()[1]] = true;

            loop:
            while (true) {

                int size = fire.size();

                while (size-- > 0) {

                    int[] f = fire.poll();

                    for (int i = 0; i < 4; i++) {
                        int nh = f[0] + move[i][0];
                        int nw = f[1] + move[i][1];

                        if (nh < 0 || nh >= h || nw < 0 || nw >= w) {
                            continue;
                        }

                        if (map[nh][nw] != '.') {
                            continue;
                        }

                        map[nh][nw] = '*';
                        fire.add(new int[] { nh, nw });
                    }
                }


                count++;

                size = point.size();
                while (size-- > 0) {
                    int[] now = point.poll();

                    for (int i = 0; i < 4; i++) {
                        int nh = now[0] + move[i][0];
                        int nw = now[1] + move[i][1];

                        if (nh < 0 || nh >= h || nw < 0 || nw >= w) {
                            escape = true;
                            break loop;
                        }

                        if (visit[nh][nw]) {
                            continue;
                        }

                        if (map[nh][nw] == '.') {
                            visit[nh][nw] = true;
                            point.add(new int[] { nh, nw });
                        }

                    }
                }

                if (point.isEmpty()) {
                    break;
                }

            }

            if (escape) {
                sb.append(count).append("\n");
            }else{
                sb.append("IMPOSSIBLE\n");
            }


        }

        System.out.println(sb.toString().trim());

    }
}

 

P.S 

요즘 Java11보다 Java 8 에서 속도가 느린 코드가 작성되고 있는것 같다.

분명 어딘가 비효율적으로 작성한 부분이 있겠지..