[Java] 백준 4179번 불!

문제

4179번: 불!

입력

• 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
• 다음 입력으로 R줄동안 각각의 미로 행이 주어진다.
• 각각의 문자들은 다음을 뜻한다.
  • #: 벽
  • .: 지나갈 수 있는 공간
  • J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
  • F: 불이 난 공간
• J는 입력에서 하나만 주어진다.

출력

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

입력 예제

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

출력 예제

3

문제 풀이

• BFS 탐색을 통해 시간별로 불을 퍼트린다.
• 불을 모두 퍼트린 후, 지훈이를 이동시키는데, 이 때, 불이 퍼져있는 곳과 벽인 곳으로 이동할 수 없으므로, 방문배열의 초기값을 0이 아닌 값으로 설정한 후, 지훈이가 이동하려는 시간보다, 불이 퍼지는 시간의 값이 더 클 때만 이동시킨다.
• 이후, 가장자리에 도달했다면, 탈출할 수 있는 경우이므로 경과시간을 출력 후 리턴하고, 가장자리에 도달하지 못했다면 "IMPOSSIBLE"을 출력한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int n;
    static int m;
    static char[][] arr;
    static int[][] fire;
    static boolean[][] visited;
    
    static ArrayList<int[]> f;
    
    static int[] dy = {-1,1,0,0};
    static int[] dx = {0,0,-1,1};
    
    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());
        arr = new char[n][m];
        fire = new int[n][m];
        
        for (int i = 0; i < n; i++) {
        	for (int j = 0; j < m; j++) {
        		fire[i][j] = Integer.MAX_VALUE;
        	}
        }
        visited = new boolean[n][m];
        f = new ArrayList<>();
        
//        int start_y = 0;
//        int start_x = 0;
        int jy = 0;
        int jx = 0;
        
        
        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            for (int j = 0; j < m; j++) {
                arr[i][j] = s.charAt(j);
                if (arr[i][j] == 'F') {
//                    arr[i][j] = '.';
                    f.add(new int[] {i,j});
                    fire[i][j] = 0;
                }
                else if (arr[i][j] == 'J') {
                    jy = i;
                    jx = j;
                }
            }
        }
        
        bfs();
//        print(fire);
        escape(jy, jx, 1);
//        print2(visited);
        
    }

    private static void escape(int jy, int jx, int time) {
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[] {jy, jx, time});
        visited[jy][jx] = true;
        while (!queue.isEmpty()) {
            int y = queue.peek()[0];
            int x = queue.peek()[1];
            int t = queue.peek()[2];
            
//            System.out.println(y + " "+ x + " "+ t);
            queue.poll();
            
//            System.out.println(y+" "+x);
            
            if (y == 0 || x == 0 || y == n - 1 || x == m - 1) {
                System.out.println(t);
//                System.out.println(y + " "+x);
                return;
            }
            for (int d = 0; d < 4; d++) {
                int ny = y + dy[d];
                int nx = x + dx[d];
                if (0 <= ny && ny < n && 0 <= nx && nx < m && !visited[ny][nx] && arr[ny][nx] != '#' && arr[ny][nx] != 'F' && fire[ny][nx] >= t + 1 ) {
//                    System.out.println(ny +" "+nx + " "+ t + 1);
                	visited[ny][nx] = true;
                    queue.add(new int[] {ny,nx, t + 1});
                }
            }
        }
        System.out.println("IMPOSSIBLE");
    }

    private static void bfs() {
        Queue<int[]> queue = new ArrayDeque<int[]>();
        for (int i = 0; i < f.size(); i++) {
            int y = f.get(i)[0];
            int x = f.get(i)[1];
//            System.out.println(y+" "+x);
            queue.add(new int[] {y,x});
        }
//        System.out.println(queue.size());
        while (!queue.isEmpty()) {
            int y = queue.peek()[0];
            int x = queue.peek()[1];
            queue.poll();
            for (int d = 0; d < 4; d++) {
                int ny = y + dy[d];
                int nx = x + dx[d];
                if (0 <= ny && ny < n && 0 <= nx && nx < m && arr[ny][nx] != 'F' && arr[ny][nx] != '#' && fire[ny][nx] == Integer.MAX_VALUE) {
                    fire[ny][nx] = fire[y][x] + 1;
                    queue.add(new int[] {ny,nx});
                }
            }
        }
        
        
    }

    private static void print(int[][] arr) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }
    }
    
    private static void print2(boolean[][] arr) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }
        
    }

}