[백준] 4179 불! - BFS JAVA

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

4179번: 불!

문제풀이

BFS 문제였습니다.

이 문제를 풀기 위해 가장 중요하게 이해해야할 점은

 

1. 불이 먼저 움직입니다.

2. 이후에 사람이 움직입니다.

(초기 Queue에 있는 값만큼 움직이고, 다시 멈춘뒤, 계속 그것을 반복합니다.)

문제에서 사람이 만약 boundary 밖으로 나가면 그 자체로 성공이니 종료시킵니다.

 

문제를 풀면서 지훈이의 위치에 불이 도달하여 map이 'F'로 초기화되지만,

이미 이동할 지훈이가 현재 위치의 Queue에 다 저장되어있으므로 상관이 없습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int R, C;
	public static char[][] map;
	public static Queue<Node> jihun_q = new LinkedList<>();
	public static Queue<Node> fire_q = new LinkedList<>();
	public static int time = 0;
	public static boolean resultflag = false;
	public static int[] dx= {-1,1,0,0};
	public static int[] dy = {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());
    	
    	R = Integer.parseInt(st.nextToken());
    	C = Integer.parseInt(st.nextToken());
    	map = new char[R][C];
 
    	for(int i=0;i<R;i++) {
    		map[i] = br.readLine().toCharArray();
    		for(int j=0;j<C;j++) {
    			if(map[i][j] == 'J') {
    				jihun_q.add(new Node(i, j));
    			}else if(map[i][j] == 'F') {
    				fire_q.add(new Node(i,j));
    			}
    		}
    	}
    	
    	
    	int time = 0;
    	while(true) {
    		time++;
    		int fire_q_size = fire_q.size();
    		for(int i=0;i<fire_q_size;i++) {
    			Node temp = fire_q.poll();
    			int x = temp.x;
    			int y = temp.y;
    			for(int dir=0;dir<4;dir++) {
    				int nx = x + dx[dir];
    				int ny = y + dy[dir];
    				if( nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
    				if(map[nx][ny] == 'J' || map[nx][ny] == '.') {
    					map[nx][ny] = 'F';
    					fire_q.offer(new Node(nx, ny));
    				}
    			}
    		}
    		
    		int jiun_q_size = jihun_q.size();
    		for(int i=0;i<jiun_q_size;i++) {
    			Node temp = jihun_q.poll();
    			int x = temp.x;
    			int y = temp.y;
    			for(int dir=0;dir<4;dir++) {
    				int nx = x + dx[dir];
    				int ny = y + dy[dir];
    				if( nx < 0 || nx >= R || ny < 0 || ny >= C) {
    					System.out.println(time);
    					return ;
    				}
    				if(map[nx][ny] == '.') {
    					jihun_q.offer(new Node(nx, ny));
    					map[nx][ny] = 'J';
    				}
    			}
    		}
    		
    		if(jihun_q.isEmpty()) {
    			System.out.println("IMPOSSIBLE");
    			return ;
    		}
    		
    		
    	}
    }
    
}
 
class Node{
	int x;
	int y;
	public Node(int x, int y) {
		this.x=x;
		this.y=y;
	}
}