[Beakjoon] 백준 5427번 불 (Java)

5427 불

 

5427번: 불

 

난이도 및 유형

난이도 : 골드 4

유형 : 그래프 탐색 / BFS / 구현

 

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다. 빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

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

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

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

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

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

출력

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

 

 

문제풀이

처음 풀이는 아래 코드처럼 BFS를 활용해서 풀이했다. 먼저, 불의 좌표를 ArrayList에 저장한다. 그리고 map[][]에 상근이의 좌표를 저장한다. 이후, BFS를 통해서 벽을 피해 상근이는 빈공간으로 이동하고 불역시 벽을 피해 빈공간으로 확산된다. 최종적으로, map[][]의 범위를 벗어나면 상근이는 탈출에 성공한다. 하지만, 이 풀이는 12%에서 계속 시간초과가 발생하며 통과하지 못했다.

 

 

[시간초과 발생 코드]

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.List;
import java.util.ArrayList;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        final int testCase = Integer.parseInt(bufferedReader.readLine());
        final StringBuilder stringBuilder = new StringBuilder();

        StringTokenizer stringTokenizer;
        char[][] map;
        String line;
        Point man = null;
        int height, width;
        List<Point> firePoints;

        for (int i = 0; i < testCase; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());

            height = Integer.parseInt(stringTokenizer.nextToken());
            width = Integer.parseInt(stringTokenizer.nextToken());
            map = new char[width][height];

            firePoints = new ArrayList<>();

            for (int j = 0; j < width; j++) {
                line = bufferedReader.readLine();

                for (int k = 0; k < height; k++) {
                    map[j][k] = line.charAt(k);

                    if (map[j][k] == '@') {
                        man = new Point(j, k);
                    }

                    if (map[j][k] == '*') {
                        firePoints.add(new Point(j, k));
                    }
                }
            }

            stringBuilder.append(findRoute(map, man, firePoints)).append("\n");
        }

        System.out.println(stringBuilder);
    }

    private static String findRoute(final char[][] map, final Point man, final List<Point> firePoints) {
        final int[] dx = {1, 0, -1, 0};
        final int[] dy = {0, 1, 0, -1};

        final Deque<Point> queue = new ArrayDeque<>();
        boolean[][] isVisited = new boolean[map.length][map[0].length];
        queue.add(man);
        isVisited[man.x][man.y] = true;
        int time = 1;

        while (!queue.isEmpty()) {
            int size = firePoints.size();

            for (int i = 0; i < size; i++) {
                final Point firePoint = firePoints.get(i);

                for (int j = 0; j < dx.length; j++) {
                    int nextX = firePoint.x + dx[j];
                    int nextY = firePoint.y + dy[j];

                    if (nextX < 0 || nextY < 0 || nextX >= map.length || nextY >= map[0].length) {
                        continue;
                    }

                    if (map[nextX][nextY] == '#' || map[nextX][nextY] == '*') {
                        continue;
                    }

                    firePoints.add(new Point(nextX, nextY));
                    map[nextX][nextY] = '*';
                }
            }

            size = queue.size();

            for (int i = 0; i < size; i++) {
                final Point point = queue.poll();

                map[point.x][point.y] = '.';

                for (int j = 0; j < dx.length; j++) {
                    int nextX = point.x + dx[j];
                    int nextY = point.y + dy[j];

                    if (nextX < 0 || nextY < 0 || nextX >= map.length || nextY >= map[0].length) {
                        return time + "";
                    }

                    if (map[nextX][nextY] == '#' || map[nextX][nextY] == '*') {
                        continue;
                    }

                    if (isVisited[nextX][nextY]) {
                        continue;
                    }

                    queue.add(new Point(nextX, nextY));
                    isVisited[nextX][nextY] = true;
                    map[nextX][nextY] = '@';
                }
            }

            time++;
        }

        return "IMPOSSIBLE";
    }

}

 

처음에는 시간초과가 왜 발생했는지 이해하지 못하고 계속 고민하던 중 질문 계시판을 확인했다. 나와 비슷한 케이스의 시간초과를 경험한 사람이 있어서 그 글을 참고하여 문제를 해결할 수 있었다. 문제의 원인은 ArrayList 였다.

 

해당 문제는 불이 퍼지는 상황을 피해서 상근이가 배열 밖의 위치로 이동할 수 있는 시간을 확인하는 문제이다. 나는 불이 확장되는 것을 구현하기 위해 ArrayList를 사용했다. 처음 불의 위치를 ArrayList에 저장하고 이를 사방탐색하면서 한 타임마다 퍼저나가도록 구현했다. 바로 이 구현에서 시간초과의 원인이 발생한 것이었다.

 

불은 한번 확산되고 map[][]에 번진 불을 표시하도록 구현했기 때문에 더 이상 ArrayList에 저장되어있을 필요가 없다. 하지만, 기존의 로직은 계속해서 ArrayList에 새로 번진 불을 추가하도록 구현했다. 때문에 BFS 탐색시 매번 처음 저장한 불의 위치부터 전부 데이터를 찾아야 하는 상황이 발생한 것이다. (ArrayList는 내부가 배열로 구현되어 있다. 배열은 데이터를 찾는데 O(N)의 시간복잡도가 걸린다.)

 

그래서 문제를 해결하기 위해 LinkedList로 구현한 Queue를 적용했다. 불의 위치를 Queue에 저장하고 BFS 탐색을 통해 불을 확산하도록 했다. 이후, 기존의 불 위치는 다시 사용하지 않기 때문에 큐에서 제거하는 방식으로 로직을 변경했다. 이렇게 시간초과 문제를 해결해 정답을 맞출 수 있었다.

 

[정답코드]

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.List;
import java.util.LinkedList;
import java.util.Deque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        final int testCase = Integer.parseInt(bufferedReader.readLine());
        final StringBuilder stringBuilder = new StringBuilder();

        StringTokenizer stringTokenizer;
        char[][] map;
        String line;
        Point man = null;
        int height, width;
        Queue<Point> firePoints;

        for (int i = 0; i < testCase; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());

            height = Integer.parseInt(stringTokenizer.nextToken());
            width = Integer.parseInt(stringTokenizer.nextToken());
            map = new char[width][height];

            firePoints = new LinkedList<>();

            for (int j = 0; j < width; j++) {
                line = bufferedReader.readLine();

                for (int k = 0; k < height; k++) {
                    map[j][k] = line.charAt(k);

                    if (map[j][k] == '@') {
                        man = new Point(j, k);
                    }

                    if (map[j][k] == '*') {
                        firePoints.add(new Point(j, k));
                    }
                }
            }

            stringBuilder.append(findRoute(map, man, firePoints)).append("\n");
        }

        System.out.println(stringBuilder);
    }

    private static String findRoute(final char[][] map, final Point man, final Queue<Point> firePoints) {
        final int[] dx = {1, 0, -1, 0};
        final int[] dy = {0, 1, 0, -1};

        final Deque<Point> queue = new ArrayDeque<>();
        boolean[][] isVisited = new boolean[map.length][map[0].length];
        queue.add(man);
        isVisited[man.x][man.y] = true;
        int time = 1;

        while (!queue.isEmpty()) {
            int size = firePoints.size();

            for (int i = 0; i < size; i++) {
                final Point firePoint = firePoints.poll();

                for (int j = 0; j < dx.length; j++) {
                    int nextX = firePoint.x + dx[j];
                    int nextY = firePoint.y + dy[j];

                    if (nextX < 0 || nextY < 0 || nextX >= map.length || nextY >= map[0].length) {
                        continue;
                    }

                    if (map[nextX][nextY] == '#' || map[nextX][nextY] == '*') {
                        continue;
                    }

                    firePoints.add(new Point(nextX, nextY));
                    map[nextX][nextY] = '*';
                }
            }

            size = queue.size();

            for (int i = 0; i < size; i++) {
                final Point point = queue.poll();

                map[point.x][point.y] = '.';

                for (int j = 0; j < dx.length; j++) {
                    int nextX = point.x + dx[j];
                    int nextY = point.y + dy[j];

                    if (nextX < 0 || nextY < 0 || nextX >= map.length || nextY >= map[0].length) {
                        return time + "";
                    }

                    if (map[nextX][nextY] == '#' || map[nextX][nextY] == '*') {
                        continue;
                    }

                    if (isVisited[nextX][nextY]) {
                        continue;
                    }

                    queue.add(new Point(nextX, nextY));
                    isVisited[nextX][nextY] = true;
                    map[nextX][nextY] = '@';
                }
            }

            time++;
        }

        return "IMPOSSIBLE";
    }

}