백준 5427 C++

백준 5427

이전에 올렸던 4179랑 똑같은 문제다. 불이 퍼지는 걸 먼저 시뮬레이션 해주고, 그 다음에 상근이를 시뮬레이션하면서 먼저 이동할 때 유망하다고 판단해서 bfs를 돌리면 되는 간단한 문제다.

#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


char map[1001][1001];
int times[1001][1001];
int T;
int R, C;


void init() {
	for (int y = 0; y < R; ++y) {
		for (int x = 0; x < C; ++x) {
			times[y][x] = 0;
		}
	}
	
}

int dy[4] = { 0,0,-1,1 };
int dx[4] = { 1,-1, 0,0, };
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> T;
	while (T--) {
		queue<pair<int, int>> Fire, Sang;
		cin >> C >> R;
		init();
		for (int y = 0; y < R; ++y) {
			for (int x = 0; x < C; ++x) {
				cin >> map[y][x];

				if (map[y][x] == '*') {
					Fire.push({ y,x });
				}
				else if (map[y][x] == '@') {
					map[y][x] = '.';
					Sang.push({ y,x });
					times[y][x] = -1;
				}
				else {
					times[y][x] = -1;
				}
			}
		}


		while (!Fire.empty()) {
			int y = Fire.front().first;
			int x = Fire.front().second;

			Fire.pop();

			for (int i = 0; i < 4; ++i) {
				int ny = y + dy[i];
				int nx = x + dx[i];

				if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
				if (map[ny][nx] == '#') continue;
				if (times[ny][nx] != -1) continue;

				times[ny][nx] = times[y][x] + 1;
				Fire.push({ ny,nx });
			}
		}


		times[Sang.front().first][Sang.front().second] = 0;
		int ans = -1;
		while (!Sang.empty()) {
			int y = Sang.front().first;
			int x = Sang.front().second;

			Sang.pop();

			int ncur = times[y][x] + 1;

			for (int i = 0; i < 4; ++i) {
				int ny = y + dy[i];
				int nx = x + dx[i];

				if (ny < 0 || nx < 0 || ny >= R || nx >= C) {
					//cout << ny << " " << nx << "\n";
					ans = ncur;
					break;
				}

				if (map[ny][nx] == '#') continue;
				if (times[ny][nx] != -1 && times[ny][nx] <= ncur) continue;
				times[ny][nx] = ncur;

				Sang.push({ ny,nx });
			}

			if (ans != -1) break;
		}

		if (ans == -1)cout << "IMPOSSIBLE\n";
		else cout << ans << "\n";
	}

	return 0;
}

BOJ 카테고리 내 다른 글 보러가기