[ Baekjoon ] #5427 불

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

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

백준 #4179 불! 문제와 결국 동일한 문제이다.

 

풀이

상근이와 불의 위치를 Queue<MapLocation> 좌표값으로 담아두고 BFS 알고리즘을 호출한다.

불을 먼저 상, 하, 좌, 우 방향으로 1초마다 번지도록 처리한 후 (map[x][y] == '.' 인 경우에만)

상근이의 위치가 끝에 도달했는지 체크 후 도달하지 않았으면

위치를 map[x][y] =='.' && visit[x][y] = 0 (방문하지 않은 지역) 조건으로 이동 시킨다.

 

상근이의 위치가 사이드에 도달했으면 결과값을 ArrayList에 담은 후 

Test Case가 모두 완료되면 결과값을 모두 출력한다.

 

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

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

public class Main {

	static int tc = 0; // 테스트 케이스
	static char map[][];
	static int visit[][];
	static Queue<MapLocation> f;
	static Queue<MapLocation> sg;
	static int w;
	static int h;
	static int sec;
	
	static ArrayList<Object> result = new ArrayList<>();
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc= new Scanner(System.in);
		
		tc = sc.nextInt();
		
		for(int i=0;i<tc;i++) {
			sec = 0;
			w = sc.nextInt(); // 너비
			h = sc.nextInt(); // 높이
			
			f = new LinkedList<>();
			sg = new LinkedList<>();
			
			map = new char[h][w];
			visit = new int[h][w];
			
			for(int j=0;j<h;j++) {
				String str = sc.next();
				for(int k=0;k<w;k++) {
					map[j][k] = str.charAt(k);
					
					if(map[j][k] == '*') {
						f.offer(new MapLocation(j, k));
					}else if(map[j][k] == '@') {
						sg.offer(new MapLocation(j, k));
						visit[j][k] = 1;
					}
				}
			}
			
			getBFS();
		}
		
		for(int i=0;i<result.size();i++) {
			System.out.println(result.get(i));
		}
	}
	
	public static void getBFS() {
		int[] xx = {-1, 0, 1, 0};
		int[] yy = {0, 1, 0, -1};
		
		while(!sg.isEmpty()) {
			
			sec++;
			
			// 불 먼저 이동
			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 < h && ay >=0 && ay < w) {
						if(map[ax][ay] == '.' || map[ax][ay] == '@') {
							map[ax][ay] = '*';
							f.offer(new MapLocation(ax, ay));
						}
					}
				}
			}
			
			// 상근이
			int person = sg.size();
			for(int i=0;i<person;i++) {
				int x = sg.peek().x;
				int y = sg.poll().y;
				
				// 상근이의 위치가 가장자리면 종료
				if(x == 0 || y == 0 || x == h-1 || y == w-1) {
					result.add(sec);
					return;
				}
				
				for(int j=0;j<4;j++) {
					int ax = x+xx[j];
					int ay = y+yy[j];
					
					if(ax >= 0 && ax < h && ay >=0 && ay < w) {
						if(map[ax][ay] == '.' && visit[ax][ay] == 0) {
							map[ax][ay] = '@';
							sg.offer(new MapLocation(ax, ay));
						}
					}
				}
			}
		}
		
		result.add("IMPOSSIBLE");
	}
}