[백준] 4179번 : 불!

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

4179번: 불!

지훈이가 미로를 통과할때 or 통과하지 못하는 경우를 위한 탈출 조건만 유의해주자!

 

처음에는 bfs함수로 두지않고 main에서 로직을 처리하고 bool 변수를 통해 종료조건을 걸어주려고 했지만, 고려하지 못한 상황이 있었는지 틀렸다고 한다. 

따라서, 함수로 따로 두고 종료시점에 바로 return cnt를 통해 해결하였다. 

#include <iostream>
#include <queue>
using namespace std;

int R, C;
char maps[1000][1000];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int visit[1000][1000];
queue <pair<int, int>> fire;
queue <pair<int, int>> jihoon;

int bfs() {
	int cnt = 0;
	while (!jihoon.empty()) {
		cnt++;
		int size = fire.size();
		while (size--) {//불 이동
			int x = fire.front().first;
			int y = fire.front().second;
			fire.pop();
			for (int i = 0; i < 4; i++) {
				int cx = x + dx[i];
				int cy = y + dy[i];
				if (cx >= 0 && cx < R && cy >= 0 && cy < C && maps[cx][cy] != '#' && maps[cx][cy] != 'F') {
					maps[cx][cy] = 'F';
					fire.push({ cx,cy });
				}
			}
		}
		size = jihoon.size();
		while (size--) {//지훈 이동 
			int x = jihoon.front().first;
			int y = jihoon.front().second;
			jihoon.pop();
			if (x == 0 || x == R - 1 || y == 0 || y == C - 1) return cnt; //가장자리에 있으면 바로 탈출 

			for (int i = 0; i < 4; i++) {
				int cx = x + dx[i];
				int cy = y + dy[i];
				if (cx >= 0 && cx < R && cy >= 0 && cy < C && maps[cx][cy] == '.' && !visit[cx][cy]) {
					visit[cx][cy] = 1;
					jihoon.push({ cx,cy });
				}
			}
		}
	}
	return -1;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> R >> C;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> maps[i][j];
			if (maps[i][j] == 'F') fire.push({ i,j });
			if (maps[i][j] == 'J') {
				jihoon.push({ i,j });
				visit[i][j] = 1;
			}
		}
	}

	int result = bfs();

	if (result != -1) cout << result << '\n';
	else cout << "IMPOSSIBLE\n";
}