문제

불!

접근 방법

지훈이가 가장자리까지 이동해야되며 그또한 최소거리로 이동해야됩니다. 그래서 bfs를 사용하여 최소거리를 구했습니다.
여기서 핵심은 불과 지훈이의 각각 queue를 이용해서 확산되거나 이동할 수 있는 경로를 저장해두었으며 불을 먼저 확산시켰습니다.

불을 먼저 확산 시킨 이유는 지훈이가 안전한 곳으로 이동하기 위함입니다. 지훈이를 먼저 이동시키면 불이 나중에 덮칠 수 있어 불을 먼저 확산 시킨 뒤 지훈이가 불이 나지 않는 곳으로 이동하도록 했습니다.

정답 코드

import java.util.*;
import java.io.*;

public class Main {
    static char [][]board;
    static int dx[] ={1,-1,0,0};
    static int dy[] ={0,0,1,-1};
    static int n,m,ans;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        ans = Integer.MAX_VALUE;

        board = new char[n][m];
        Queue<int []> jihunQueue = new LinkedList<>();
        Queue<int []> fireQueue = new LinkedList<>();

        int jihun[] = new int[2];

        for(int i=0;i<n;i++){
            String s = br.readLine();
            for(int j=0;j<m;j++){
                char c = s.charAt(j);
                board[i][j] = c;

                if(c == 'J'){
                    jihun = new int[]{i,j,0};
                    jihunQueue.add(jihun);
                }else if(c == 'F'){
                    fireQueue.add(new int[]{i,j});
                }

            }
        }

        boolean visited[][] = new boolean[n][m];
        visited[jihun[0]][jihun[1]] = true;
        jihunQueue.offer(new int[]{jihun[0],jihun[1],0});

        while(!jihunQueue.isEmpty()){

            // 불 확산
            int fireSize = fireQueue.size();
            for (int i = 0; i < fireSize; i++) {
                int[] fire = fireQueue.poll();
                for (int d = 0; d < 4; d++) {
                    int nx = fire[0] + dx[d];
                    int ny = fire[1] + dy[d];
                    if (0 <= nx && nx < n && 0 <= ny  && ny < m && board[nx][ny] == '.') {
                        board[nx][ny] = 'F';
                        fireQueue.offer(new int[]{nx, ny});
                    }
                }
            }

            //지훈 이동
            int len = jihunQueue.size();

            for(int i=0;i<len;i++){
                int jihunPos[] = jihunQueue.poll();

                //가장자리에 도착할 때 밖으로 이동 +1
                if(jihunPos[0] == 0 ||jihunPos[0] == n-1 || jihunPos[1] == 0|| jihunPos[1] == m-1 ){
                    System.out.println(jihunPos[2] +1 );
                    return;
                }

                for(int d =0; d<4;d++)
                {
                    int nx = jihunPos[0] + dx[d];
                    int ny = jihunPos[1] + dy[d];

                    if( 0<= nx && nx < n && 0<= ny && ny < m && !visited[nx][ny])
                    {
                        if(board[nx][ny] == '.')
                        {
                            visited[nx][ny] = true;
                            jihunQueue.offer(new int[]{nx,ny,jihunPos[2]+1});
                        }

                    }
                }
            }
        }
        System.out.println("IMPOSSIBLE");
    }
}