백준 5427 c++ "불" -PlusUltraCode-

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

 

[필자 사고]

처음에는 매번 currentTime이 갱신되면 불의 위치를 sprayFire()함수를 통해 갱신해젔다. 

그런데 시간 초과가 났다. 생각해보니 현재 N,M의 크기가 1000정도가 된다. 

매번 1000정도를 하게 되면 시간초과가 날 수 밖에 없다.

 

방법을 바꿔보자

fire관련 된 기록들을 BFS탐색을 이용해 한번에 하게 하고 방문핳 것을 시간 즉 숫자를 기록해 놓으면

해당 문제를 타파할 수 있다. 

 

이런 아이디어를 배울 수 있어서 좋은 문제라고 생각한다.

[코드 해설]

Input()

• 입력을 받고, 초기 상태를 설정하는 함수입니다.
• 맵의 크기 N, M을 입력받고, 맵(arr), 불의 도착 시간(fireTime), 사람 방문 여부(visited)를 초기화합니다.
• 불(*)의 위치는 fireQueue에 넣고, 불의 시작 시간을 0으로 설정합니다.
• 사람(@)의 위치는 startPoint에 저장합니다.

---

isInside(y, x)

• 좌표 (y, x)가 맵 내부에 존재하는지를 확인하는 함수입니다.
• 범위를 벗어났는지 체크합니다.

---

isEscape(y, x)

• 사람이 해당 좌표 (y, x)에서 탈출할 수 있는지를 확인하는 함수입니다.
• 맵의 가장자리인 경우 탈출 가능한 위치로 판단합니다.

---

bfsFire()

• 불의 확산을 BFS 방식으로 진행하는 함수입니다.
• fireQueue에 들어있는 모든 불의 위치를 기준으로, 4방향으로 확산시킵니다.
• 벽(#)은 확산 불가능하며, 이미 방문한 위치는 건너뜁니다.
• 확산된 위치에는 불 도착 시간 = 이전 시간 + 1을 기록합니다.

---

bfsHuman(sy, sx)

• 사람의 이동을 BFS로 처리하는 함수입니다.
• 큐에 현재 위치와 시간 정보를 저장하며 진행합니다.
• 사람이 맵 가장자리(isEscape)에 도달하면 탈출 시간 + 1을 출력하고 종료합니다.
• 이동하려는 위치에 불이 이미 도착해 있거나 도착 예정인 경우(fireTime <= 현재 시간 + 1)는 이동할 수 없습니다.
• 벽이나 이미 방문한 위치도 제외하고, 가능한 곳에 대해 큐에 넣어 다음 이동을 준비합니다.
• 큐가 모두 비워질 때까지 탈출하지 못하면 "IMPOSSIBLE"을 출력합니다.

---

Game_Start()

• 불의 확산(bfsFire)과 사람의 이동(bfsHuman)을 순서대로 실행하는 함수입니다.
• 반드시 불이 먼저 확산되어야, 사람의 이동 시 불을 피할 수 있습니다.

---

main()

• 테스트 케이스의 수 T를 입력받고, 각 테스트 케이스마다 Input()과 Game_Start()를 호출합니다.
• 입출력 최적화를 위해 ios::sync_with_stdio(false), cin.tie(0) 등을 설정합니다.

[소스 코드]

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

typedef pair<int, int> Node;
struct queueNode {
	int sero, garo, size;
};

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

int T, N, M;
vector<vector<char>> arr;
vector<vector<int>> fireTime;
vector<vector<bool>> visited;
queue<queueNode> fireQueue;
Node startPoint;

void Input() {
	arr.clear();
	fireTime.clear();
	visited.clear();
	queue<queueNode> empty;
	swap(fireQueue, empty);

	cin >> M >> N;
	arr.assign(N, vector<char>(M));
	fireTime.assign(N, vector<int>(M, -1));
	visited.assign(N, vector<bool>(M, false));

	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		for (int k = 0; k < M; k++) {
			char ch = str[k];
			arr[i][k] = ch;

			if (ch == '@') startPoint = { i, k };
			if (ch == '*') {
				fireQueue.push({ i, k, 0 });
				fireTime[i][k] = 0;
			}
		}
	}
}

bool isInside(int y, int x) {
	return y >= 0 && y < N && x >= 0 && x < M;
}

bool isEscape(int y, int x) {
	// 가장자리에서 탈출 가능
	return y == 0 || y == N - 1 || x == 0 || x == M - 1;
}

void bfsFire() {
	while (!fireQueue.empty()) {
		auto [y, x, t] = fireQueue.front(); fireQueue.pop();

		for (int d = 0; d < 4; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];
			if (!isInside(ny, nx)) continue;
			if (arr[ny][nx] == '#') continue;
			if (fireTime[ny][nx] != -1) continue;

			fireTime[ny][nx] = t + 1;
			fireQueue.push({ ny, nx, t + 1 });
		}
	}
}

void bfsHuman(int sy, int sx) {
	queue<queueNode> q;
	q.push({ sy, sx, 0 });
	visited[sy][sx] = true;

	while (!q.empty()) {
		auto [y, x, t] = q.front(); q.pop();

		if (isEscape(y, x)) {
			cout << t + 1 << "\n";
			return;
		}

		for (int d = 0; d < 4; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];
			if (!isInside(ny, nx)) continue;
			if (arr[ny][nx] == '#' || visited[ny][nx]) continue;

			// 불이 먼저 도달한 경우는 이동 불가
			if (fireTime[ny][nx] != -1 && fireTime[ny][nx] <= t + 1) continue;

			visited[ny][nx] = true;
			q.push({ ny, nx, t + 1 });
		}
	}

	cout << "IMPOSSIBLE\n";
}

void Game_Start() {
	bfsFire();
	bfsHuman(startPoint.first, startPoint.second);
}

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

	cin >> T;
	while (T--) {
		Input();
		Game_Start();
	}
}