백준 4179. 불! :: 돼지개발자

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

"불먼저 사람먼저 두 번의 BFS, 트리의 level을 카운터로"

지훈이가 불을 피해 가장자리 까지 가서 몇번 만에 탈출할 수 있는지 최단거리를 구하는 문제이다. 이 문제에서 중요한 것은 불과 지훈이용 큐 두개를 가지고 BFS를 두번 돌리는 것이다. 불을 먼저 보내고 그 후에 지훈이가 갈 수 있는 경로를 탐색해야함을 주의한다. 순서가 중요하다.

이동 횟수는 count 변수를 두어 BFS 전체에서 구한다. 이 값이 트리의 level 이라고 할 수 있다. 이 때 fs,ms 와 같은 size 변수를 두어 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 R,C;
    static char[][] map;
    static boolean[][] visited;
    static Queue<Node> man = new LinkedList<>();
    static Queue<Node> fire = new LinkedList<>();
    static int min = -1;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        
        map = new char[R][C];
        visited = new boolean[R][C];
        
        for (int i = 0; i < R; i++) {
            char[] temp = br.readLine().toCharArray();
            for (int j = 0; j < C; j++) {
                map[i][j] = temp[j];
                if(temp[j] == 'J') {
                    visited[i][j] = true;
                    map[i][j] = '.';
                    man.add(new Node(i, j));
                }
                else if (temp[j] == 'F') {
                    visited[i][j] = true;
                    fire.add(new Node(i, j));
                }
            }
        }
        
        int cnt = 0;
        
        loop :while(!man.isEmpty()) {
            // fire
            int fs = fire.size();
            
            for (int s = 0; s < fs; s++) {
                Node cur = fire.poll();
                
                for (int i = 0; i < 4; i++) {
                    int nx = cur.x + dx[i];
                    int ny = cur.y + dy[i];
                    
                    if(!isRange(nx, ny) || map[nx][ny] != '.')
                        continue;
                    map[nx][ny] = 'F';
                    fire.add(new Node(nx, ny));
                }
            }
            
            // man
            int ms = man.size();
            
            for (int s = 0; s < ms; s++) {
                Node cur = man.poll();
                
                for (int i = 0; i < 4; i++) {
                    int nx = cur.x + dx[i];
                    int ny = cur.y + dy[i];
                    
                    if(!isRange(nx, ny)) {
                        min = ++cnt;
                        break loop;
                    }
                    
                    if(visited[nx][ny] || map[nx][ny] != '.')
                        continue;
                    visited[nx][ny] = true;
                    man.add(new Node(nx, ny));
                }
            }
            cnt++;
        }
        System.out.println(min == -1 ? "IMPOSSIBLE" : min);
    }
    
    static boolean isRange(int x, int y) {
        if( x < 0 || x >= R || y <  0 || y >= C) return false;
        return true;
    }
 
}
 
class Node {
    int x;
    int y;
    
    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}