[ Baekjoon ] #4179 불!

[Baekjoon][https://www.acmicpc.net/problem/4179]

너비 우선 탐색(BFS) 알고리즘

지훈이와 불의 위치를 Queue에 담고 BFS 알고리즘을 호출 해서 처리.

지훈이의 위치가 Queue에 존재할 때까지 BFS 알고리즘을 호출하며,

불의 위치 먼저 상, 하, 좌, 우로 1분마다 번지도록 처리한다.

지훈이의 위치는 visit[x][y] == 0 (방문하지 않은 위치) && map[x][y] == '.' 위치로만 이동이 가능하며,

끝자락에 도달했을 대의 분+1 값을 출력한다.

 

아래 이미지는 예제1의 1분마다 로직이 처리되었을때를 출력해보았다.

[예제 입력1]

4 4

########
#JF#
#..#
#..#

[예제 입력1]

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Location{
	
	int x;
	int y;
	
	public Location(int x, int y) {
		// TODO Auto-generated constructor stub
		this.x = x;
		this.y = y;
	}
}

public class Main {

	static int r;
	static int c;
	static char map[][];
	static int minute = 0;
	static int visit[][];
	static Queue<Location> jh; // 지훈 좌표값
	static Queue<Location> f; // 불 좌표값
	static boolean flag = true;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		r = sc.nextInt(); // 높이
		c = sc.nextInt(); // 가로
		
		map = new char[r][c];
		visit = new int[r][c];
		jh = new LinkedList<>();
		f = new LinkedList<>();
		
		for(int i=0;i<r;i++) {
			String str = sc.next();
			for(int j=0;j<c;j++) {
				map[i][j] = str.charAt(j);
				
				if(map[i][j] == 'F') {
					f.offer(new Location(i, j));
				} else if(map[i][j] == 'J') {
					jh.offer(new Location(i, j));
					visit[i][j] = 1;
				}
			}
		}
		
		getBFS();
	}
	
	public static void getBFS()	{
		
		int[] xx = {-1, 0, 1, 0};
		int[] yy = {0, 1, 0, -1};
		
		while(!jh.isEmpty()) {
			int fire_size = f.size();
			
			for(int i=0;i<fire_size;i++) {
				int x = f.peek().x;
				int y = f.poll().y;
				
				for(int j=0;j<4;j++) {
					int ax = x+xx[j];
					int ay = y+yy[j];
					
					if(ax > 0 && ax < r && ay > 0 && ay < c) {
						if(map[ax][ay] == '.' || map[ax][ay] == 'J') {
							map[ax][ay] = 'F';
							f.offer(new Location(ax, ay));
						}
					}
				}
			}
			
			int person = jh.size();
			for(int i=0;i<person;i++) {
				int x = jh.peek().x;
				int y = jh.poll().y;
				
				if(x == 0 || x == r-1 || y == 0 || y == c-1) {
					minute++;
					System.out.println(minute);
					return;
				}
				
				for(int j=0;j<4;j++) {
					int ax = x + xx[j];
					int ay = y + yy[j];
					
					if(ax >= 0 && ax < r && ay >= 0 && ay < c) {
						if(map[ax][ay] == '.' && visit[ax][ay] == 0) {
							map[ax][ay] = 'J';
							jh.offer(new Location(ax, ay));
							visit[ax][ay] = 1;
						}
					}
				}
			}
		
			minute++;
		}
		
		if(flag) {
			System.out.println("IMPOSSIBLE");
		}
	}
}