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

Problem 🔒

문제

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

 

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

예제 입력 1

4 4
####
#JF#
#..#
#..#

예제 출력 1

3

---

Approach ⭕

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

---

Solution 💡

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

public class 불4179 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int R=sc.nextInt(), C=sc.nextInt(), sec=0;
        int[][] map = new int[R][C], visit = new int[R][C];
        Queue<int[]> fire = new LinkedList<>(), jihoon = new LinkedList<>();
        int[] dr = {0,0,1,-1}, dc = {1,-1,0,0};
        boolean pos = true;

        for(int i=0; i<R; i++){
            String str = sc.next();
            for(int j=0; j<C; j++){
                map[i][j] = str.charAt(j);
                if(map[i][j]=='J'){
                    map[i][j] = '.';
                    visit[i][j] = 1;
                    jihoon.add(new int[]{i,j});
                }
                if(map[i][j]=='F') fire.add(new int[]{i,j});
            }
        }

        loopOut :
        while (true){
            sec++;

            // 불 번짐
            int fireSize = fire.size();
            for(int i=0; i<fireSize; i++){
                int[] f = fire.poll();
                for(int d=0; d<4; d++){
                    int nr = f[0] + dr[d];
                    int nc = f[1] + dc[d];

                    if(nr>=0 && nr<R && nc>=0 && nc<C && map[nr][nc]=='.'){
                        map[nr][nc] = 'F';
                        fire.add(new int[]{nr, nc});
                    }
                }
            }

            // 지훈이 이동
            int jiSize = jihoon.size();

            // 탈출할 수 없는 경우
            if(jiSize==0){
                pos = false;
                break loopOut;
            }

            for(int i=0; i<jiSize; i++){
                int[] j = jihoon.poll();

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

                    // 탈출한 경우(경계에 도달한 경우)
                    if(nr<0 || nr>=R || nc<0 || nc>=C) break loopOut;

                    if(visit[nr][nc]==0 && map[nr][nc]=='.'){
                        visit[nr][nc] = 1;
                        jihoon.add(new int[]{nr, nc});
                    }
                }
            }

        }// while

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

    }
}

---

Tips❣️

• 탈출 성공 여부 확인 : 다음 이동할 위치가 맵 경계를 벗어난 경우(반복문 종료)
• 탈출 실패 여부 확인 : 지훈이의 위치를 담은 큐가 비어있으면 지훈이가 더이상 이동할 위치가 없다는 뜻으로 탈출이 불가능한 경우(반복문 종료)

결과

 

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

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