[백준] 5427 불 - BFS(너비우선탐색) + 구현(Implementation) JAVA

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

5427번: 불

코드설명

BFS(너비우선탐색) + 구현(Implementation) 를 활용하는 문제입니다.

 

1. 불과 사람의 초기 위치를 큐에 저장합니다.
2. 불이 번지는 시뮬레이션을 수행하면서 불의 위치를 갱신합니다.
3. 사람이 이동하는 시뮬레이션을 수행하면서 사람의 위치를 갱신합니다.
4. 사람이 출구에 도달하거나 큐가 비어 불이 모두 번진 경우에 시뮬레이션을 종료합니다.

 

simulate(): 불과 사람의 이동 시뮬레이션을 수행하는 메소드입니다. 불과 사람이 각각 이동하면서 맵을 갱신하고, 사람이 출구에 도달하면 이동한 횟수를 반환합니다.

 

문제에서 유의해야할 사항은, 종료조건입니다.

- 사람이 출구에 도달하거나,

- PeopleQ에 아무값도 없다면

- 이동횟수가 H*W 를 넘어가거나

위의 3가지 정도의 종료조건을 구현해주었습니다.

더 이상 이동할 수 없으므로 종료를 시킴으로써 적정한 시점에 IMPOSSIBLE을 출력할 수 있습니다.

코드

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 {
	public static int W, H;
	public static int answer = 0;
	public static char[][] map;
	public static Queue<Node> fireQ = new LinkedList<>();
	public static Queue<Node> peopleQ = new LinkedList<>();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());

    	int T= Integer.parseInt(st.nextToken());
    	
    	for(int t = 0; t < T; t ++) {
    		st = new StringTokenizer(br.readLine());
    		W = Integer.parseInt(st.nextToken());
        	H = Integer.parseInt(st.nextToken());
        	map = new char[H][W];
        	
        	peopleQ = new LinkedList<Node>();
        	fireQ = new LinkedList<Node>();
        	for(int i=0;i<H;i++) {
        		st = new StringTokenizer(br.readLine());
        		String str = st.nextToken();
        		for(int j=0;j<W;j++) {
        			map[i][j] = str.charAt(j);
        			
        			if(map[i][j] == '@') {
        				peopleQ.add(new Node(i, j, 0));
        			}
        			else if(map[i][j] == '*' ) {
        				fireQ.add(new Node(i, j, 0));
        			}
        		}
        	}
        	answer = -1;
        	answer = simulate();
        	if(answer == -1)
        		System.out.println("IMPOSSIBLE");
        	else 
        		System.out.println(answer);
    	}
    	
    }
    
    public static int simulate() {
    	int[] dx = {-1,1,0,0};
    	int[] dy = {0,0,-1,1};
    	
    	boolean successFlag = false;
    	int moveCnt = 0;
    	while(successFlag == false && moveCnt <= H*W) {
    		moveCnt += 1;
    		
    		if(peopleQ.isEmpty()) {
    			break;
    		}
    		
    		int fireQSize = fireQ.size();
    		int fireCnt = 0;
    		while(!fireQ.isEmpty()) {
        		Node temp = fireQ.poll();
        		
        		for(int dir = 0; dir < 4; dir++) {
        			int nr = temp.r + dx[dir];
        			int nc = temp.c + dy[dir];
        			if(nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
        			if(map[nr][nc] == '#') continue;
        			if(map[nr][nc] == '*') continue;
        			
        			map[nr][nc] = '*';
        			fireQ.offer(new Node(nr, nc, 0));
        		}
        		fireCnt += 1;
        		
        		if(fireQSize == fireCnt) {
        			fireCnt = 0;
        			fireQSize = fireQ.size();
        			break;
        		}
        	}
        	
        	int peopleQSize = peopleQ.size();
        	int peopleCnt = 0;
        	while(!peopleQ.isEmpty()) {
        		
        		Node temp = peopleQ.poll();
        		for(int dir = 0; dir < 4; dir++) {
        			int nr = temp.r + dx[dir];
        			int nc = temp.c + dy[dir];
        			//만약 범위밖으로 나간다면 성공이다.
        			if(nr < 0 || nr >= H || nc < 0 || nc >= W) {
        				successFlag = true;
        				return temp.cnt + 1;
        			}
        			if(map[nr][nc] == '#') continue;
        			if(map[nr][nc] == '*') continue;
        			if(map[nr][nc] == '@') continue;
        			
        			map[nr][nc] = '@';
        			peopleQ.offer(new Node(nr, nc, temp.cnt + 1));
        		}
        		peopleCnt += 1;
        		if(peopleQSize == peopleCnt) {
        			peopleQSize = peopleQ.size();
        			peopleCnt = 0;
        			break;
        		}
        	}
        	
    	}
    	
    	
    	return -1;
    	
    }
}
class Node{
	int r;
	int c;
	int cnt;
	public Node(int r, int c, int cnt) {
		this.r = r;
		this.c = c;
		this.cnt = cnt;
	}
}