[백준/Java] #5427 불

✏️ 불 

사용 언어 : Java
레벨 : 골드 4
📎https://www.acmicpc.net/problem/5427

 

🔎 문제 설명

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

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

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

 

📌 입력과 출력 

입력

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

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

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

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

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

 

출력

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

 

💻 입출력 예

 

⚒️ 풀이

 

문제를 보고 나서 BFS를 쓰면 된다는 것을 깨달아서 바로 BFS 코드를 짜기 시작했다. 다만, 문제점은 불의 BFS 와 상근이의 BFS를 동시에 돌려야한다는 점인데 전에 불! 문제를 풀었을 때와 조건이 비슷해서 불 BFS를 먼저 돌리고, 상근이의 BFS를 돌리면 풀 수 있는 문제였던 것 같다. 다른 BFS 문제와 다르게 크게 어려운 점은 없었는데, 아무래도 두 BFS를 동시에 돌려야 하다 보니 시간 안에 풀 수 있을지가 조금 걱정이 되었다. 일단 코드를 다 작성한뒤 예제 입출력과 같은 결과값이 나오는 것을 확인하고는 제출을 해봤다.

 

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

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

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static int bfs() throws IOException {
        String[] input = br.readLine().split(" ");
        int w = Integer.parseInt(input[0]);
        int h = Integer.parseInt(input[1]);
        String[][] building = new String[h][w];
        Queue<Pair> person = new LinkedList<>(); // 상근 bfs
        Queue<Pair> fire = new LinkedList<>(); // 불 bfs
        int[][] move = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        for (int i = 0; i < h; i++) {
            input = br.readLine().split("");
            for (int j = 0; j < w; j++) {
                if (input[j].equals("@")) {
                    person.add(new Pair(i, j));
                } else if (input[j].equals("*")) {
                    fire.add(new Pair(i, j));
                }

                building[i][j] = input[j];
            }
        }

        int time = 0;
        while (!person.isEmpty() && !fire.isEmpty()) {
            int fireSize = fire.size();
            time++;

            for (int k = 0; k < fireSize; k++) {
                Pair cur = fire.poll();
                for (int i = 0; i < 4; i++) {
                    int nx = cur.x + move[i][0];
                    int ny = cur.y + move[i][1];
                    if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
                    if (building[nx][ny].equals("*") || building[nx][ny].equals("#")) continue;
                    building[nx][ny] = "*";
                    fire.add(new Pair(nx, ny));
                }
            }

            int personSize = person.size();

            for(int k = 0; k < personSize; k++) {
                Pair cur = person.poll();
                for (int i = 0; i < 4; i++) {
                    int nx = cur.x + move[i][0];
                    int ny = cur.y + move[i][1];
                    if(nx < 0 || ny < 0 || nx >= h || ny >= w) {
                        return time;
                    }
                    if(building[nx][ny].equals("*") || building[nx][ny].equals("#")) continue;
                    building[nx][ny] = "@";
                    person.add(new Pair(nx, ny));
                }
            }

        }
        return -1;
    }
    public static void main(String[] args) throws IOException {
        int testCaseNum = Integer.parseInt(br.readLine());

        for(int t = 0; t < testCaseNum; t++) {
            int time = bfs();
            bw.write(time == -1 ? "IMPOSSIBLE\n" : time + "\n");
        }

        bw.close();
    }
}

 

결론은 메모리 초과가 나왔는데 코드를 분석한 결과, 크게 벗어나지는 않는 것 같아서 최대한 연산량을 줄일 수 있는 부분이 뭐가 있을지 찾아보다가 

if(building[nx][ny].equals("*") || building[nx][ny].equals("#")) continue;

 

이 부분을 굳이 이렇게 할 필요가 없고 이동할 수 있는 땅이 아닌 경우만 찾으면 되지 않나? 싶어서 

if(!building[nx][ny].equals(".")) continue;

 

이렇게 코드를 변경해주었더니 작동은 잘 했으나... 틀렸습니다. 가 나왔다. 내가 틀렸던 부분은 12% 였고 처음엔 반례를 나 혼자서 찾아보려고 이것저것 넣어봤었는데 잘 못찾겠어서 백준의 질문게시판을 이용하게 되었다.

생각보다 12%에서 틀리신 분이 많아서 반례는 쉽게 찾을 수 있었다.

10 5
##########
#@....#*.#
#.....#..#
#.....#..#
##.#######

 

바로 이 반례였는데 불은 벽에 가로막혀서 더 이상 이동하지 못하고 상근이는 계속 이동하다가 탈출을 하는 예제에서 정답은 5가 나와야하는데 내 코드의 경우 IMPOSSIBLE 이 나오는 상황이였다.

코드를 분석한 결과 while 문의 조건을 두 queue 가 비어있지 않는 상황에서만 bfs가 돌도록 코드를 짜버려서, 불의 BFS가 끝나니까 while문을 빠져나오게 되면서 time을 제대로 계산해도 마지막에 -1을 리턴하게 되는 것이였다.

while (!person.isEmpty() || !fire.isEmpty()) {

 

while 문 조건을 OR 문으로 변경하고 제출을 하니..!

 

맞았습니다!! 가 뜨는 모습!

 

 

생각보다 조금 헷갈렸던 문제인 것 같은데 BFS에 대해 잘 알고 있고 실수만 하지 않는다면 충분히 풀 수 있는 문제인 것 같다!

 

최종 코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

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

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static int bfs() throws IOException {
        String[] input = br.readLine().split(" ");
        int w = Integer.parseInt(input[0]);
        int h = Integer.parseInt(input[1]);
        String[][] building = new String[h][w];
        Queue<Pair> person = new LinkedList<>(); // 상근 bfs
        Queue<Pair> fire = new LinkedList<>(); // 불 bfs
        int[][] move = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        for (int i = 0; i < h; i++) {
            input = br.readLine().split("");
            for (int j = 0; j < w; j++) {
                if (input[j].equals("@")) {
                    person.add(new Pair(i, j));
                } else if (input[j].equals("*")) {
                    fire.add(new Pair(i, j));
                }

                building[i][j] = input[j];
            }
        }

        int time = 0;
        while (!person.isEmpty() || !fire.isEmpty()) {
            int fireSize = fire.size();
            time++;

            for (int k = 0; k < fireSize; k++) {
                Pair cur = fire.poll();
                for (int i = 0; i < 4; i++) {
                    int nx = cur.x + move[i][0];
                    int ny = cur.y + move[i][1];
                    if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
                    if (building[nx][ny].equals("*") || building[nx][ny].equals("#")) continue;
                    building[nx][ny] = "*";
                    fire.add(new Pair(nx, ny));
                }
            }

            int personSize = person.size();

            for(int k = 0; k < personSize; k++) {
                Pair cur = person.poll();
                for (int i = 0; i < 4; i++) {
                    int nx = cur.x + move[i][0];
                    int ny = cur.y + move[i][1];
                    if(nx < 0 || ny < 0 || nx >= h || ny >= w) {
                        return time;
                    }
                    if(!building[nx][ny].equals(".")) continue;
                    building[nx][ny] = "@";
                    person.add(new Pair(nx, ny));
                }
            }
        }
        return -1;
    }
    public static void main(String[] args) throws IOException {
        int testCaseNum = Integer.parseInt(br.readLine());

        for(int t = 0; t < testCaseNum; t++) {
            int time = bfs();
            bw.write(time == -1 ? "IMPOSSIBLE\n" : time + "\n");
        }

        bw.close();
    }
}