[백준] 5427번 : 불 - 자바(Java)

Problem 🔒

문제

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

 

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

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

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

입력

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

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

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

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

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

출력

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

예제 입력 1

5
4 3
####
#*@.
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
7 4
###.###
#....*#
#@....#
.######
5 5
.....
.***.
.*@*.
.***.
.....
3 3
###
#@#
###

예제 출력 1

2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE

---

Approach 1 ❌

DFS로 접근해 불이 번진 후 상근이가 이동할 수 있는 모든 경로를 탐색하여 탈출할 수 있는지와 몇 초가 걸렸는지 확인하여 최소 시간을 갱신하는 방법으로 풀려고 했었다.

하지만 DFS로 풀면, 재귀적으로 경로를 탐색하고 다시 되돌아오는 경우를 처리하는게 힘들다고 생각했다.

이 문제는 상근이가 가장 빠르게 탈출하는 시간을 구하는게 핵심이기 때문에, BFS를 사용하여 최단 경로를 찾는게 더 바람직했다.

---

Approach 2⭕

1. 입력 및 초기 위치 설정
   • 상근이의 초기 위치는 방문 처리하고, ‘.’(빈 공간)으로 저장하여 불이 이동 가능하게 처리한다.
   • 상근이와 불의 위치를 각각 큐에 저장한다.
2. 매 초마다 BFS를 기반으로 2가지 상황 진행
   1. 불 확산 시키기
      • 현재 큐에 존재하는 모든 불의 위치에 대해 동서남북 방향으로 불을 퍼뜨린다.
      • 불이 퍼질 수 있는 위치는 맵 경계를 넘지 않고, 빈 공간이어야 한다.
      • 불이 퍼진 위치는 다시 큐에 넣고, 다음 루프에서 퍼질 수 있도록 한다.
   2. 상근이 대피
      • 현재 큐에 존재하는 모든 상근이의 위치에 대해 동서남북 방향으로 이동한다.
      • 상근이는 이전에 방문하지 않은 위치와 빈 공간으로만 이동할 수 있다.
      • 이동 가능한 위치이면 방문 처리하고, 큐에 넣어 이동을 이어갈 수 있도록 한다.

---

Solution 💡

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 불 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int t=0; t<T; t++){
            int W = sc.nextInt(); int H = sc.nextInt();
            char[][] map = new char[H][W];
            int[][] visit = new int[H][W]; // 상근이 방문했는지

            Queue<int[]> sangQ = new LinkedList<>(); // 상근이 위치 저장
            Queue<int[]> fireQ = new LinkedList<>(); // 불 위치 저장
            int[] dr = {0, 0, 1, -1}; int[] dc = {1, -1, 0, 0};

            for(int i=0; i<H; i++){
                String str = sc.next();
                for(int j=0; j<W; j++){
                    map[i][j] = str.charAt(j);

                    if(map[i][j]=='@'){
                        map[i][j] = '.'; // 상근이 위치 빈 공간으로 입력
                        visit[i][j] = 1; // 방문 표시
                        sangQ.add(new int[]{i,j});
                    }
                    if(map[i][j]=='*'){
                        fireQ.add(new int[]{i,j});
                    }
                }
            }

            int sec = 0; // 탈출시간
            boolean pos = true; // 탈출가넝?

            loopOut :
            while(true){
                sec++;

                // 불 번지기
                int qsize1 = fireQ.size();
                for(int i=0; i<qsize1; i++){
                    int[] fire = fireQ.poll(); // 불 위치 하나 꺼내
                    for(int d=0; d<4; d++){
                        int nr = fire[0] + dr[d];
                        int nc = fire[1] + dc[d];

                        if(nr>=0 && nr<H && nc>=0 && nc<W && map[nr][nc]=='.'){
                            map[nr][nc] = '*';
                            fireQ.add(new int[]{nr, nc});
                        }
                    }
                }

                // 상근이 대피
                int qsize2 = sangQ.size();
                if(qsize2==0) {
                    pos = false;
                    break loopOut;
                }
                for(int i=0; i<qsize2; i++){
                    int[] sang = sangQ.poll(); // 상근이 위치 하나 꺼내
                    // 상근이가 출구로 왔는지 확인
                    if(sang[0]==0 || sang[0]==H-1 || sang[1]==0 || sang[1]==W-1) break loopOut;

                    for(int d=0; d<4; d++){
                        int nr = sang[0] + dr[d];
                        int nc = sang[1] + dc[d];

                        if(nr>=0 && nr<H && nc>=0 && nc<W && visit[nr][nc]==0 && map[nr][nc]=='.'){
                            visit[nr][nc] = 1;
                            sangQ.add(new int[]{nr, nc});
                        }
                    }
                }

            }

            if(pos){
                System.out.println(sec);
            }else{
                System.out.println("IMPOSSIBLE");
            }

        }// 테스트 케이스

    }
}

---

Tip❣️

• H, W 입력 값이 H, W 순이 아니라 W, H 순으로 주어진다.
• 탈출 성공 여부 확인 : 큐에서 꺼낸 상근이의 위치가 경계인 경우(반복문 종료)
• 탈출 실패 여부 확인 : 상근이의 위치를 담은 큐가 비어있으면 상근이가 더이상 이동할 위치가 없다는 뜻으로 탈출이 불가능한 경우(반복문 종료)

결과

 

4179번 불! 문제와 완전히 같은 문제여서, 4179번으로 다시 복습하면 좋을 것 같다.

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