백준 5427 C++ (BFS)

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

5427번: 불

2차원 BFS문제다.

 

불의 경우를 먼저 탐색하고 상근의 경우를 탐색한후 거리를 비교해서 판단한다.

구현 방법

1. '*' 좌표에서 탐색을 시작하기 위해 해당 좌표를 큐(QF)에 넣음.
2. '@' 좌표에서 탐색을 시작하기 위해 해당 좌표를 큐(QS)에 넣음
3. 큐(QF)에서 원소를 꺼내 우측, 좌측, 전방, 후방, 위, 아래 인접한 칸에 대해 4번 탐색함.
4. 해당 칸이 범위 밖인경우, 방문했거나(거리가 0 이상) 벽인경우('#') 건너뜀.
5. 큐가 빌때까지 반복.
6. 큐(QS)에서 원소를 꺼내 우측, 좌측, 전방, 후방, 위, 아래 인접한 칸에 대해 4번 탐색함.
7. 다음 칸이 범위 밖(탈출 성공)인 경우 현재 좌표까지의 거리를 출력하고 break.
8. 다음 칸이 벽이거나 방문했을경우 건너뜀.
9. 다음 칸이 불이 지나가고 상근이가 간 거리보다 작거나 같은경우 넘어감.
10. 큐가 빌때까지 반복하고 큐가 비었음에도 탈출하지 못했다면 Trapped 출력.

코드로 살펴보자.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <tuple>
#include <cstring>
using namespace std;

// 탐색 방향
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
// 입력 받을 맵
char board[1002][1002];
// 상근의 거리
int distS[1010][1010];
// 불의 거리
int distF[1010][1010];

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

	int t;
	cin >> t;
	while (t--) {
		int w, h;
		cin >> w >> h;
		// 불의 큐
		queue<pair<int, int>> QF; 
        // 상근의 큐
		queue<pair<int, int>> QS;

		bool isEscape = false;
        
		// dist 모두 -1로 초기화
		for (int i = 0; i < h; i++) {
			fill(distF[i], distF[i] + w, -1); 
			fill(distS[i], distS[i] + w, -1); 
		}
        // 입력
		for(int i = 0; i < h; i++)
			for (int j = 0; j < w; j++) {
				cin >> board[i][j];
                // 불의 좌표를 큐에 넣고 dist 0으로 초기화
				if (board[i][j] == '*') {
					QF.push({ i,j });
					distF[i][j] = 0;
				}
				// 상근의 좌표를 큐에 넣고 dist 0으로 초기화
				if (board[i][j] == '@') {
					QS.push({ i,j });
					distS[i][j] = 0;
				}
			}
		// 불의 경우 먼저
		while (!QF.empty()) 
		{
			pair <int, int> cur = QF.front(); 
			QF.pop(); 
			
            // 좌우전후 4방향 탐색
			for (int dir = 0; dir < 4; dir++) { 
				int nx = cur.first + dx[dir];  
				int ny = cur.second + dy[dir]; 
				// 범위를 벗어나는 경우 넘어감
				if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
                // 이미 방문했거나, 벽인경우 넘어감
				if (distF[nx][ny] >= 0 || board[nx][ny] == '#') continue;

				distF[nx][ny] = distF[cur.first][cur.second] + 1;  
				QF.push({ nx, ny }); 
			}
		}

		// 상근의 경우
		while (!QS.empty()) 
		{
			pair <int, int> cur = QS.front(); 
			QS.pop(); 

			for (int dir = 0; dir < 4; dir++) { 
				int nx = cur.first + dx[dir]; 
				int ny = cur.second + dy[dir]; 
				// 범위를 벗어남 : 탈출
				if (nx < 0 || nx >= h || ny < 0 || ny >= w) {
					isEscape = true;
					cout << distS[cur.first][cur.second] + 1 << '\n';
					break;
				}

				if (distS[nx][ny] >= 0 || board[nx][ny] == '#') continue;
				// 
				if (distF[nx][ny] != -1 && distS[cur.first][cur.second] + 1 >= distF[nx][ny]) continue;

				distS[nx][ny] = distS[cur.first][cur.second] + 1;  
				QS.push({ nx, ny });  
			}
            // 위의 for문이 남았을 경우 while문을 나가는 break를 추가해줘야함.
			if (isEscape)
				break;
		}
		if (!isEscape)
			cout << "IMPOSSIBLE" << '\n';
	}
	return 0;
}