[백준] 5427번 불 (C++, JAVA)

5427번: 불

모든 불을 먼저 인접한 빈 공간을 검사한 뒤

그 공간을 불로 바꿔준다.

그다음 내가 갈 수 있는 인접한 빈 공간을 찾은 뒤

이전 공간의 값(이전 공간까지 가는데 걸린 시간) + 1한 값을 넣어준다.

 

내가 갈 수 있는 빈 공간이 없는 경우는 IMPOSSIBLE이고

내 위치가 빌딩의 가장자리인 경우엔 그 시간을 출력해준다.

 

< C++ 코드 >

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
int X, Y, x, y, success = -1;
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
void Bfs(queue <pair<int, int>> me, queue <pair<int, int>> fire, char building[][1001], bool visited[][1001], int res[][1001], int h, int w) {
	while (1) {
		X = me.front().first, Y = me.front().second;
		if ((X == 0 && Y < w) || (Y == 0 && X < h) || (X == h - 1 && Y < w) || (Y == w - 1 && X < h)) {
			success = res[X][Y];
			break;
		}
		queue <pair<int, int>> q;
		while (!fire.empty()) {
			for (int i = 0; i < 4; i++) {
				x = fire.front().first + dx[i], y = fire.front().second + dy[i];
				if (x >= 0 && x < h && y >= 0 && y < w && (building[x][y] == '.' || building[x][y] == '@')) {
					building[x][y] = '*';
					q.push(pair<int, int>(x, y)); //임시 큐에 push
				}
			}
			fire.pop();
		}

		while (!q.empty()) { //불 담는 큐에 옮기기
			fire.push(pair<int, int>(q.front().first, q.front().second));
			q.pop();
		}

		while (!me.empty()) {
			for (int i = 0; i < 4; i++) {
				X = me.front().first, Y = me.front().second;
				x = X + dx[i], y = Y + dy[i];
				if (x >= 0 && x < h && y >= 0 && y < w && visited[x][y] == false && building[x][y] == '.') {
					visited[x][y] = true;
					res[x][y] = res[X][Y] + 1;
					q.push(pair<int, int>(x, y)); //임시 큐에 push
					if ((x == 0 && y < w) || (y == 0 && x < h) || (x == h - 1 && y < w) || (y == w - 1 && x < h)) {
						success = res[x][y];
						break;
					}
				}
			}
			me.pop();
		}
		if (success != -1) break;
		while (!q.empty()) { //나를 담는 큐에 옮기기
			me.push(pair<int, int>(q.front().first, q.front().second));
			q.pop();
		}
		if (me.empty()) break;
	}
	
}

int main() {
	int T, w, h;
	cin >> T;
	string a;
	for (int t = 0; t < T; t++) {
		char building[1001][1001];
		bool visited[1001][1001] = { false };
		int res[1001][1001] = { 0 };
		queue <pair<int, int>> me, fire;
		cin >> w >> h;
		for (int i = 0; i < h; i++) {
			cin >> a;
			for (int j = 0; j < w; j++) {
				building[i][j] = a[j];
				if (a[j] == '@') {
					x = i, y = j;
					me.push(pair<int, int>(x, y)); //시작 위치 넣어놓는다
				}
				else if (a[j] == '*') {
					visited[i][j] = true;
					fire.push(pair<int, int>(i, j)); //불 위치 넣어놓는다
				}
			}
		}
		
		Bfs(me, fire, building, visited, res, h, w);
		if (success == -1) cout << "IMPOSSIBLE\n";
		else cout << success + 1 << "\n";
		success = -1;
	}

	return 0;
}

 

< JAVA 코드 >

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

public class BOJ_5427_불 {
	private static int T, W, H, res;
	private static int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
	private static char arr[][];
	private static boolean fired[][], been[][];
	private static Queue <int[]> fire = new LinkedList<>();
	private static Queue <int[]> escaper = new LinkedList<>();
	
	public static boolean bfs(int time) {
		while(!fire.isEmpty()) {
			if(fire.peek()[2] > time) break; // 불 이동 끝나면 나감
			for(int i = 0; i < 4; i++) {
				int x = fire.peek()[0] + dx[i], y = fire.peek()[1] + dy[i];
				if(x < 0 || x >= H || y < 0 || y >= W || fired[x][y] || arr[x][y] == '#') continue;
				fired[x][y] = true; // 불 방문 체크
				fire.offer(new int[] {x, y, time + 1});
			}
			fire.poll();
		}
		while(!escaper.isEmpty()) {
			if(escaper.peek()[2] > time) break; // 상근이 이동 끝나면 나감
			for(int i = 0; i < 4; i++) {
				int x = escaper.peek()[0] + dx[i], y = escaper.peek()[1] + dy[i];
				if(x < 0 || x >= H || y < 0 || y >= W) { // 범위를 벗어나면 탈출 성공
					res = time + 1;
					return true;
				}
				if(been[x][y] || arr[x][y] == '#' || fired[x][y]) continue; // 이미 갔던 곳이거나 벽이 있거나 불이 있으면 안 감
				been[x][y] = true; // 상근이 방문 체크
				escaper.offer(new int[] {x, y, time + 1});
			}
			escaper.poll();
		}
		return false;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		for(int t = 1; t <= T; t++) {
			W = sc.nextInt(); H = sc.nextInt(); res = -1;
			arr = new char[H][W]; fired = new boolean[H][W]; been = new boolean[H][W];
			
			for(int i = 0; i < H; i++) {
				String st = sc.next();
				for(int j = 0; j < W; j++) {
					arr[i][j] = st.charAt(j);
					if(arr[i][j] == '@') {
						been[i][j] = true;
						escaper.offer(new int[] {i, j, 0});
					}
					else if(arr[i][j] == '*') {
						fired[i][j] = true;
						fire.offer(new int[] {i, j, 0});
					}
				}
			} // 입력

			while(!escaper.isEmpty()) {
				if(bfs(escaper.peek()[2])) break; // 탈출 성공이면 더 이상 계산할 필요가 없음
			}
			
			while(!escaper.isEmpty()) escaper.poll();
			while(!fire.isEmpty()) fire.poll(); // 다음 테스트 케이스를 위해 초기화
			
			if(res == -1) System.out.println("IMPOSSIBLE");
			else System.out.println(res);
		}
	}
}