4179번 문제 불! 자바(JAVA) 풀이

문제

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

4179번: 불!

풀이 코드

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

/**
 * 불이 퍼지는 속도를 BFS로 구하고,
 * 사람이 이동하는 속도를 BFS로 구한다.
 * 단, 사람은 같은 장소를 불보다 나중에 오거나 동시에 올 수 없다.
 */
public class Main {
    
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int R = Integer.parseInt(st.nextToken()); //미로의 행
        int C = Integer.parseInt(st.nextToken()); //미로의 열
        
        char[][] map = new char[R][C]; //미로
        int[][] visit = new int[R][C]; //사람의 방문
        int[][] burn = new int[R][C]; //불의 방문

        Queue<int[]> person = new LinkedList<>(); //사람 큐
        Queue<int[]> fire = new LinkedList<>(); //불 큐
        
        for (int i = 0; i < R; i++) {
            String str = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = str.charAt(j);

                if (map[i][j] == 'J') { //사람인 경우
                    person.offer(new int[]{i, j}); //사람 큐에 넣는다.
                    visit[i][j] = 1; //사람 방문 표시
                } else if (map[i][j] == 'F') { //불인 경우
                    fire.offer(new int[]{i, j}); //불 큐에 넣는다.
                    burn[i][j] = 1; //불 방문 표시
                }
            }
        }

        //불 BFS
        while (!fire.isEmpty()) {
            int size = fire.size();
            for (int i = 0; i < size; i++) {
                int[] curPoint = fire.poll();
                int x = curPoint[0];
                int y = curPoint[1];
                for (int j = 0; j < 4; j++) {
                    int nx = x + dx[j];
                    int ny = y + dy[j];
                    
                    //범위를 벗어나거나 벽이거나 이미 방문했으면 pass
                    if (nx < 0 || ny < 0 || nx >= R || ny >= C || map[nx][ny] == '#' || burn[nx][ny] != 0) continue;
                    burn[nx][ny] = burn[x][y] + 1; //방문 표시 겸 시간
                    fire.offer(new int[]{nx, ny}); //다음 좌표를 불 큐에 넣는다.
                }
            }
        }

        //사람 BFS
        while (!person.isEmpty()) {
            int size = person.size();
            for (int i = 0; i < size; i++) {
                int[] curPoint = person.poll();
                int x = curPoint[0];
                int y = curPoint[1];
                for (int j = 0; j < 4; j++) {
                    int nx = x + dx[j];
                    int ny = y + dy[j];

                    //범위를 벗어나면 탈출
                    if (nx < 0 || ny < 0 || nx >= R || ny >= C) {
                        System.out.println(visit[x][y]);
                        return;
                    }

                    //이미 방문 했거나 벽이거나 불보다 먼저 못 왔으면 pass
                    if (visit[nx][ny] != 0 || map[nx][ny] == '#' || visit[x][y] + 1 >= burn[nx][ny] && burn[nx][ny] != 0) continue;
                    visit[nx][ny] = visit[x][y] + 1; //방문 표시 겸 시간
                    person.offer(new int[]{nx, ny}); //사람 큐에 넣는다.
                }
            }
        }

        //여기까지 왔으면 탈출 못하는 것을 의미
        System.out.println("IMPOSSIBLE");
    }
}