백준 5427 - 불

문제

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

리뷰

https://velog.io/@mj3242/%EB%B0%B1%EC%A4%80-4179-%EB%B6%88

위 문제와 같은 로직으로 풀이할 수 있는 문제였다.

다만, 이 문제에서는 각각의 테스트케이스에 대해 가능할 경우 최단 시간 혹은
IMPOSSIBLE 을 도출해야 하기에 하나의 테스트케이스에 대해 bfs 를
수행할 때마다 sQueue 와 fQueue 를 clear() 해주어야 했다.

로직의 시간복잡도는 $O(w*h)$의 형태이므로 최악의 경우에도 100만의
연산을 수행하여 주어진 제한 조건인 1초를 무난하게 통과한다.

코드

import java.util.*;

import static java.lang.Integer.parseInt;


public class Main {
    static int h, w;
    static int[] px = {-1, 1, 0, 0};
    static int[] py = {0, 0, -1, 1};

    static char[][] map;
    static Queue<Node> sQueue = new ArrayDeque<>();
    static Queue<Node> fQueue = new ArrayDeque<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = parseInt(in.nextLine());

        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        while (T-- > 0) {
            st = new StringTokenizer(in.nextLine());
            w = parseInt(st.nextToken());
            h = parseInt(st.nextToken());

            map = new char[h][w];
            for (int y = 0; y < h; y++) {
                String line = in.nextLine();
                for (int x = 0; x < w; x++) {
                    map[y][x] = line.charAt(x);
                    if (map[y][x] == '@')
                        sQueue.offer(new Node(x, y, 0));
                    else if (map[y][x] == '*')
                        fQueue.offer(new Node(x, y, 0));
                }
            }

            int result = bfs();
            sb.append(result == -1 ? "IMPOSSIBLE" : result).append("\n");
            sQueue.clear();
            fQueue.clear();
        }

        System.out.print(sb);
        in.close();
    }

    static int bfs() {
        int level = 0;
        int nx, ny;

        while (!sQueue.isEmpty()) {
            while (!sQueue.isEmpty() && sQueue.peek().level == level) {
                Node currentS = sQueue.poll();

                if (map[currentS.y][currentS.x] == '*')
                    continue;

                for (int i = 0; i < px.length; i++) {
                    nx = currentS.x + px[i];
                    ny = currentS.y + py[i];

                    if (!isValid(nx, ny))
                        return currentS.level + 1;

                    if (isValid(nx, ny) && map[ny][nx] == '.') {
                        map[ny][nx] = '@';
                        sQueue.add(new Node(nx, ny, currentS.level + 1));
                    }
                }
            }

            while (!fQueue.isEmpty() && fQueue.peek().level == level) {
                Node currentF = fQueue.poll();

                for (int i = 0; i < px.length; i++) {
                    nx = currentF.x + px[i];
                    ny = currentF.y + py[i];

                    if (isValid(nx, ny) && map[ny][nx] != '#' && map[ny][nx] != '*') {
                        map[ny][nx] = '*';
                        fQueue.add(new Node(nx, ny, currentF.level + 1));
                    }
                }
            }

            level++;
        }

        return -1;
    }

    static boolean isValid(int x, int y) {
        return x >= 0 && x < w && y >= 0 && y < h;
    }

    static class Node {
        int x, y, level;

        public Node(int x, int y, int level) {
            this.x = x;
            this.y = y;
            this.level = level;
        }
    }
}

결과