[백준]4179: 불!(java)

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

4179번: 불!

문제

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

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

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

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

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

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

입력

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

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

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

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

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

출력

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

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

 

예제 입력 1 

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

예제 출력 1 

3

---

풀이

시뮬레이션 + bfs 문제였다.

불을 퍼트린다 > 지훈이가 이동한다를 반복해주면된다.

이때 불과 지훈이의 방문을 모두 다 처리해줘야한다.

전체 코드

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

public class BJ_G4_4179_불 {
    static class Pos{
        int x;
        int y;

        Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int N, M;
    static char[][] map;
    static Queue<Pos> jihunQ = new LinkedList<>();
    static Queue<Pos> fireQ = new LinkedList<>();
    static boolean[][] jihunVisited;
    static boolean[][] fireVisited;
    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());
        map = new char[N][M];
        jihunVisited = new boolean[N][M];
        fireVisited = new boolean[N][M];
        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<M; j++) {
                map[i][j] = str.charAt(j);
                if(map[i][j] == 'J') {
                    map[i][j] = '.';
                    jihunQ.add(new Pos(i, j));
                    jihunVisited[i][j] = true;
                } else if(map[i][j] == 'F') {
                    fireQ.add(new Pos(i, j));
                    fireVisited[i][j] = true;
                }
            }
        }

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

    private static void bfs() {
        int[][] dist = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int time = 0;

        while(!jihunQ.isEmpty()) {
            int jihunLen = jihunQ.size();
            int fireLen = fireQ.size();
            for(int i=0; i<fireLen; i++) {
                Pos fire = fireQ.poll();
                for(int d=0; d<4; d++) {
                    int nx = fire.x + dist[d][0];
                    int ny = fire.y + dist[d][1];

                    if(!isIn(nx, ny) || map[nx][ny] == '#' || fireVisited[nx][ny]) continue;
                    fireVisited[nx][ny] = true;
                    map[nx][ny] = 'F';
                    fireQ.add(new Pos(nx, ny));
                }
            }
            for(int i=0; i<jihunLen; i++) {
                Pos jihun = jihunQ.poll();
                for(int d=0; d<4; d++) {
                    int nx = jihun.x + dist[d][0];
                    int ny = jihun.y + dist[d][1];

                    if(!isIn(nx, ny)) {
                        time++;
                        System.out.println(time);
                        System.exit(0);
                    }

                    if(map[nx][ny] !='.' || jihunVisited[nx][ny]) continue;
                    jihunVisited[nx][ny] = true;
                    jihunQ.add(new Pos(nx, ny));
                }
            }

            time++;
        }
    }

    private static boolean isIn(int x, int y){
        return 0<=x && x<N && 0<=y && y<M;
    }
}