백준 - 4179번 불!

문제

매 분마다 한칸씩 수평또는 수직으로 이동하는 불과 지훈!
지훈이가 몇 초만에 미로를 탈출 할 수 있을까?

생각

네 방향으로 확산되고, 미로 최소 탈출 시간을 출력해라 bfs지!

맨 처음에는 불을 bfs돌면서 몇 초에 불이 퍼지는지 map에 표시를 해놓는 걸 생각했는데,
그냥 큐에 불이랑 지훈이를 같이 넣어놓고 퍼뜨리면 되더라!

그래서 큐에 count, x, y를 가지고 다니면서
지훈이는 count를 ++ 해가면서 불은 count를 --해가면서 bfs하다가
맵 밖으로 빠져나가면 결과 반환하도록 작성했다

주의해야 할 점

1. 같은 시간에 불이랑 지훈이가 퍼질 수 있는 곳엔, 지훈이가 갈 수 없음!
   큐에 불을 먼저 넣어줘서 뒤에 지훈이가 갈 수 없게하자!

2. for문을 사용해서 네 방향으로 퍼지는걸 구현했는데,
   맵 밖으로 나가면 result = count + 1을 하고 break를 하도록 한 게 for문만 탈출하고
   큐 도는 while문은 탈출하지 않아서 result 값이 최소가 아닌 문제가 있었다!
   while문 안에도 result값을 보고 break하는 걸 해줘야한다!

코드

#define _CRT_SECURE_NO_WARNINGS

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

using namespace std;

//가장 빠른 bfs

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

int map[1005][1005]; // 갈 수 있는 곳 0 , 벽 1

int checkJ[1005][1005]; // 방문했던 곳은 1로 표시
int checkF[1005][1005]; // 불이 퍼진 곳은 1로 표시

queue < pair<int, pair<int, int>>> q; //현재 소요 시간, x, y값 //현재 소요시간이 음수면 불!

int main(int argc, char** argv)
{
	int r, c;
	int x, y;

	cin >> r >> c;

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			char temp;
			cin >> temp;

			if (temp == 'F') {
				checkF[i][j] = 1;
				q.push({ -1, {i,j} });
			}
			else if (temp == '#') {
				map[i][j] = 1;
			}
			else if (temp == 'J') {
				x = i;
				y = j;
			}
		}
	}

	//불 넣고 지훈이 넣고 bfs 돌려!
	int result = -1;
	checkJ[x][y] = 1;
	q.push({ 0,{x, y} });

	while (!q.empty()) {
		int count = q.front().first;
		int nowX = q.front().second.first;
		int nowY = q.front().second.second;
		q.pop();

		if (result != -1) {
			break;
		}

		for (int i = 0; i < 4; i++) {
			int nextX = nowX + dx[i];
			int nextY = nowY + dy[i];

			if (nextX < 0 || nextY < 0 || nextX >= r || nextY >= c) {
				if (count < 0) {
					continue;
				}
				else {
					result = count + 1;
					break;
				}
			}

			if (count < 0) {
				if (map[nextX][nextY] == 0 && checkF[nextX][nextY] == 0) {
					checkF[nextX][nextY] = 1;
					q.push({ count - 1, {nextX, nextY} });
				}
			}
			else {
				if (map[nextX][nextY] == 0 && checkJ[nextX][nextY] == 0 && checkF[nextX][nextY] == 0) {
					checkJ[nextX][nextY] = 1;
					q.push({ count + 1, {nextX, nextY} });
				}
			}
		}
	}

	if (result == -1) {
		cout << "IMPOSSIBLE";
	}
	else {
		cout << result;
	}

	return 0;
}