백준 5427번 C++

백준 5427번 불

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

5427번: 불

정답 코드

#include<iostream>
#include<queue>
using namespace std;
char arr[1001][1001];
int time1[1001][1001];
int time2[1001][1001];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
void bfs() {
	queue<pair<int, int>>q1;
	queue<pair<int, int>>q2;
	int w, h;
	cin >> w >> h;

	for (int i = 0; i < 1001; i++) {
		for (int j = 0; j < 1001; j++) {
			time1[i][j] = -1;
			time2[i][j] = -1;
		}
	}

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == '*') {
				time1[i][j] = 0;
				q1.push({ i,j });
			}
			else if (arr[i][j] == '@') {
				time2[i][j] = 0;
				q2.push({ i,j });
			}
		}
	}

	while (!q1.empty()) { // 불
		pair<int, int>cur = q1.front();
		q1.pop();
		for (int dir = 0; dir < 4; dir++) {
			int mx = cur.first + dx[dir];
			int my = cur.second + dy[dir];
			if (mx < 0 || my < 0 || mx >= h || my >= w)
				continue;
			if (arr[mx][my] == '#' || time1[mx][my] >= 0)
				continue;
			time1[mx][my] = time1[cur.first][cur.second] + 1;
			q1.push({ mx,my });
		}
	}

	while (!q2.empty()) { //상근이
		pair<int, int>cur = q2.front();
		q2.pop();
		for (int dir = 0; dir < 4; dir++) {
			int mx = cur.first + dx[dir];
			int my = cur.second + dy[dir];
			if (mx < 0 || my < 0 || mx >= h || my >= w) {
				cout << time2[cur.first][cur.second] + 1;
				return;
			}
			if (arr[mx][my] == '#' || time2[mx][my] >= 0)
				continue;
			if (time1[mx][my] != -1 && time1[mx][my] <= time2[cur.first][cur.second] + 1)
				continue;
			time2[mx][my] = time2[cur.first][cur.second] + 1;
			q2.push({ mx,my });
		}
	}
	cout << "IMPOSSIBLE";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int test;
	cin >> test;
	for (int x = 0; x < test; x++) {
		bfs();
		cout << '\n';
	}
}

문제 풀이

불이 확산되는 것과 상근이가 이동하는 것을 분리해서 생각했습니다. 그리고 불이 먼저 확산되는 것을 bfs로 만든 후 상근이가 이동할 때 이것을 고려하게 만들었습니다. 그래서 time배열을 2개를 만들었습니다. 불이 확산되는 부분은 배열의 범위와 이미 방문한 곳, 벽을 고려하였습니다. 상근이가 움직이는 것은 벽인 곳, 이미 방문한 곳, 벽은 아니지만 불이 확산될 수 있는 곳을 고려하였고 배열의 범위를 벗어나면 그때의 시간을 출력하였습니다.