[백준] 4179 불! (JAVA)

문제 링크:

4179번: 불!

 

 

난이도: 골드3

 

 

문제:

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

 

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

 

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

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

 

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

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

 

 

입력:

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

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

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

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

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

 

 

출력:

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

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

 

 

문제이해:

지훈이는 불이 번지는 미로 안에 있다. 매 분마다 지훈이와 불은 상하좌우로 한 칸씩 이동한다. 불은 벽을 못 넘고, 지훈이도 마찬가지다. 불은 계속 번지고, 지훈이는 불보다 먼저 움직여야 산다. 지훈이가 미로의 가장자리에 닿으면 바로 탈출이다. 목표는 지훈이가 탈출할 수 있는지, 있다면 최소 시간이 몇 분인지 구하는 것이다.

 

예시로 이해해보자

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

미로 그림을 머릿속에 그려보면, (2,2)에 지훈이 J, (2,3)에 불 F가 있다.

시간별로 불이 어떻게 확산되는지 확인하면 다음과 같다.

t=0
####
#JF#
#..#
#..#

t=1
####
#FF#
#.F#
#..#

t=2
####
#FF#
#FF#
#.F#

t=3
####
#FF#
#FF#
#FF#

이걸 보면 (4,2)는 t=3에 불이 도착한다. 지훈이는 (2,2)→(3,2)→(4,2)로 t=2에 가장자리 칸 도착, 다음 한 걸음에 밖으로 나가니 정답 3이 된다.

 

 

구현방향:

이를 구현하기 위해서 불부터 멀티소스 BFS로 돌린다. 미로 안의 모든 불 시작점을 동시에 큐에 넣고, 벽을 제외한 칸들에 대해 가장 빨리 불이 도착하는 시간을 칸별로 계산해 둔다.

 

그다음 지훈이에 대해 BFS를 돌린다. 한 번에 한 칸씩 넓혀 가되, 들어가려는 칸에 도착하려는 시각이 그 칸의 불 도착 시각보다 반드시 더 빠를 때만 이동한다. 동시에 도착하면 이동 불가로 본다. 이 BFS는 본질적으로 최단 시간을 보장한다.

 

지훈이의 BFS가 가장자리 칸에 닿는 순간, 바로 바깥으로 한 걸음 더 나간다고 보고 그때까지의 시간을 탈출 시간으로 기록한다. 끝까지 가장자리에 닿지 못하면 불가능을 출력한다.

 

시작 지점이 가장자리면 답은 1이다. 불이 여러 곳이면 그대로 멀티소스 BFS로 처리된다. 전체 절차는 두 번의 BFS라 격자 크기에 비례하는 시간에 끝난다.

 

이를 코드로 그대로 구현하면 다음과 같다.

 

 

정답코드:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static char[][] matrix;
    static int[][] dist;
    static int[][] fireTime;
    static boolean [][]fireVisited;
    static boolean [][]visited;
    static int startX,startY;
    static int startFireX,startFireY;
    static int resultX, resultY; //미로를 나가기전 마지막 위치

    public static void fireTimeBFS(int x, int y){
        Queue<int[]> q=new LinkedList<>();

        //fireTime/visited 초기화 + INF 세팅
        for (int i=0;i<N;i++){
            for (int j=0;j<M;j++){
                fireVisited[i][j] = false;
                fireTime[i][j] = 1000000000;
            }
        }

        for (int i=0;i<N;i++){
            for (int j=0;j<M;j++){
                if (matrix[i][j] == 'F') {
                    fireVisited[i][j] = true;
                    fireTime[i][j] = 0;
                    q.add(new int[]{i, j});
                }
            }
        }
        while(!q.isEmpty()) {
            int[] cur = q.poll();
            int curX = cur[0];
            int curY = cur[1];

            // 상
            if (curX > 0 && !fireVisited[curX - 1][curY] && matrix[curX-1][curY] != '#') {
                fireVisited[curX - 1][curY] = true;
                fireTime[curX-1][curY]=fireTime[curX][curY]+1;
                q.add(new int[]{curX-1, curY });
            }
            // 하
            if (curX + 1 < N && !fireVisited[curX + 1][curY] && matrix[curX+1][curY] != '#') {
                fireVisited[curX + 1][curY] = true;
                fireTime[curX+1][curY]=fireTime[curX][curY]+1;
                q.add(new int[]{curX+1, curY});
            }
            // 좌
            if (curY > 0 && !fireVisited[curX][curY - 1] && matrix[curX][curY-1] != '#') {
                fireVisited[curX][curY - 1] = true;
                fireTime[curX][curY-1]=fireTime[curX][curY]+1;
                q.add(new int[]{curX, curY - 1});
            }
            // 우
            if (curY + 1 < M && !fireVisited[curX][curY + 1] && matrix[curX][curY+1] != '#'){
                fireVisited[curX][curY + 1] = true;
                fireTime[curX][curY+1]=fireTime[curX][curY]+1;
                q.add(new int[]{curX, curY + 1});
            }
        }
    }

    public static int bfs(int x, int y){
        Queue<int[]> q=new LinkedList<>();
        visited[x][y]=true;
        dist[x][y]=0;
        q.add(new int[]{x,y});

        while(!q.isEmpty()) {
            int[] cur = q.poll();
            int curX = cur[0];
            int curY = cur[1];

            //탈출할 수 있는지 확인
            if (curX == 0 || curX == N - 1 || curY == 0 || curY == M - 1) {
                resultX=curX;
                resultY=curY;
                return dist[curX][curY] + 1;
            }

            //상
            if (curX > 0 && !visited[curX - 1][curY]
                    && (matrix[curX-1][curY]=='.'||matrix[curX-1][curY]=='J')) {
                int nx = curX-1, ny = curY;
                int nextT = dist[curX][curY] + 1;
                if (fireTime[nx][ny] > nextT) {
                    q.add(new int[]{nx, ny});
                    dist[nx][ny]=nextT;
                    visited[nx][ny]=true;
                }
            }
            //하
            if (curX + 1 < N && !visited[curX + 1][curY]
                    && (matrix[curX+1][curY]=='.'||matrix[curX+1][curY]=='J')) {
                int nx = curX+1, ny = curY;
                int nextT = dist[curX][curY] + 1;
                if (fireTime[nx][ny] > nextT) {
                    q.add(new int[]{nx, ny});
                    dist[nx][ny]=nextT;
                    visited[nx][ny]=true;
                }
            }
            //좌
            if (curY > 0 && !visited[curX][curY - 1]
                    && (matrix[curX][curY-1]=='.'||matrix[curX][curY-1]=='J')) {
                int nx = curX, ny = curY-1;
                int nextT = dist[curX][curY] + 1;
                if (fireTime[nx][ny] > nextT) {
                    q.add(new int[]{nx, ny});
                    dist[nx][ny]=nextT;
                    visited[nx][ny]=true;
                }
            }
            //우
            if (curY + 1 < M && !visited[curX][curY + 1]
                    && (matrix[curX][curY+1]=='.'||matrix[curX][curY+1]=='J')){
                int nx = curX, ny = curY+1;
                int nextT = dist[curX][curY] + 1;
                if (fireTime[nx][ny] > nextT) {
                    q.add(new int[]{nx, ny});
                    dist[nx][ny]=nextT;
                    visited[nx][ny]=true;
                }
            }
        }
        return 0;
    }

    public static void main(String[] args) throws IOException {
        //초기세팅
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        N=Integer.parseInt(st.nextToken());
        M=Integer.parseInt(st.nextToken());

        matrix=new char[N][M];
        visited=new boolean[N][M];
        fireVisited=new boolean[N][M];
        dist=new int[N][M];
        fireTime=new int[N][M];

        for (int i=0; i<N; i++){
            StringBuilder sb=new StringBuilder(br.readLine());
            for (int j=0; j<M; j++){
                matrix[i][j]=sb.charAt(j);
                //시작 위치 기억
                if(matrix[i][j]=='J'){
                    startX=i;
                    startY=j;
                }
                //불 시작위치 기억
                if(matrix[i][j]=='F'){
                    startFireX=i;
                    startFireY=j;
                }
            }
        }

        //탐색시작
        fireTimeBFS(startFireX,startFireY);
        int ans = bfs(startX, startY);

        //결과출력
        if(ans==0 || ans-1>=fireTime[resultX][resultY]){
            System.out.println("IMPOSSIBLE");
        }
        else{
            System.out.println(ans);
        }
    }
}

 

 

마무리하며:

이 문제에서 불 F는 여러 개일 수 있다. 불은 여러 시작점에서 동시에 퍼지도록 멀티소스 BFS를 먼저 돌려서, 각 칸에 불이 처음 닿는 시간을 한 번에 구해두는 게 핵심이라 생각한다.

 

감사합니다.