불 [백준 5427][골드4][Java]

 

[광고 누르면 오늘의 행운 상승!!]

 

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

 

5427번: 불

BFS 시뮬레이션 문제

(포인트는 동시에 퍼져나간다 + 불이 먼저 퍼져나가야 한다) -> 두개의 큐를 이용한다.

1. Fireq와 q에 각각 불의 위치와 사람의 위치를 넣는다.

2. 큐를 각각 돌려서 불먼저 퍼져나가게 한 후 사람이 이동하게 한다.

3. 사람의 최소 이동경로를 ans에 저장한다.

package Study0307;

import java.io.*;
import java.util.*;

class Position{
	int row, col, cnt;
	public Position(int row, int col,int cnt) {
		this.row = row;
		this.col = col;
		this.cnt = cnt;
	}
	public Position(int row, int col) {
		this.row = row;
		this.col = col;
	}
}
public class 불 {
	public static final int[] dx = {1,0,-1,0};
	public static final int[] dy = {0,1,0,-1};
	public static int N,M,ans;
	public static boolean[][] visit;
	public static char[][] map;
	public static Queue<Position> q;
	public static Queue<Position> Fireq;
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int T = Integer.parseInt(st.nextToken());
		
		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			
			M = Integer.parseInt(st.nextToken());
			N = Integer.parseInt(st.nextToken());
			
			map = new char[N][M];
			visit = new boolean[N][M];
			q = new LinkedList<>();
			Fireq = new LinkedList<>();
			
			for (int i = 0; i < N; i++) {
				char[] ch = br.readLine().toCharArray();
				for (int j = 0; j < M; j++) {
					map[i][j] = ch[j];
					if		(map[i][j] == '*') Fireq.add(new Position(i,j));
					else if (map[i][j] == '@') q.add(new Position(i,j,0));
				}
			}
			ans = 0;
			bfs();
			if(ans == 0) System.out.println("IMPOSSIBLE");
			else  	     System.out.println(ans);
		}
	}
	public static void bfs() {
		
		int size = 0;
		while(!q.isEmpty()) {
			size = Fireq.size();
			for (int f = 0; f < size; f++) {
				Position fire = Fireq.poll();
				for (int i = 0; i < 4; i++) {
					int nx = fire.row + dx[i];
					int ny = fire.col + dy[i];
					
					if((nx<0 || nx >=N || ny <0 || ny>= M)) {
						continue;
					}
					
					if(map[nx][ny] == '.' || map[nx][ny] == '@') {
						map[nx][ny] = '*';
						Fireq.add(new Position(nx,ny));
					}
				}
			}
			size = q.size();
			for (int h = 0; h < size; h++) {
				Position pos = q.poll();
				for (int i = 0; i < 4; i++) {
					int nx = pos.row + dx[i];
					int ny = pos.col + dy[i];
					
					if((nx<0 || nx >=N || ny <0 || ny>= M)) {
						ans = pos.cnt+1;
						return;
					}
					
					if(map[nx][ny] == '.') {
						map[nx][ny] = '@';
						q.add(new Position(nx,ny,pos.cnt+1));
					}
				}
			}
		}
	}
}