개요

백준 5427: 불

• 입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

'.': 빈 공간
'#': 벽
'@': 상근이의 시작 위치
'*': 불
각 지도에 @의 개수는 하나이다.

• 출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

접근 방식

1. bfs를 두 개를 사용하였다.
2. 일단 두 가지 방법이 떠올랐는 데,
   1. 상근이가 최단 거리로 탈출했을 때 시간 저장 후, 해당 지점으로 불길이 도착 했을때의 시간을 비교하는 방법.
   2. 불이 옮겨질 예정인 칸에는 상근이가 못가므로, 불을 bfs방식으로
      레벨 1만큼 진행 시킨 후, 상근이도 레벨 1만큼 진행시키며 탈출 시키기.
3. 2번 방법은 상근이가 탈출했거나 탈출 불가능할 때 bfs함수가 중지되지만,
   1번 방법은 불과 상근이를 따로 bfs함수를 실행하므로, 중간에 중지되지 않아서 비효율적일것 같아서 2번 방법을 이용하여 풀었다.

코드

#include<iostream>
#include<queue>

using namespace std;

//#,@,.,*입력받는 배열
char building[1001][1001];
//상근이가 갈수있는 좌표 담는 큐(bfs에서)
queue<pair<int,int>> person;
//상근이가 움직인 좌표의 방문여부
int visitedP[1001][1001];
//불이 옮겨붙는 좌표 담는 큐(bfs에서 사용)
queue<pair<int,int>> fire;
//불이 옮겨붙는 좌표 방문 여부
int visitedF[1001][1001];

//상하좌우 좌표 반복문처리하기위한 배열
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};

//열, 행
int width = 0, height = 0;

void solution();

/// <summary>
/// 방문 배열, 큐 초기화
/// </summary>
void init() {
	fill(&visitedF[0][0], &visitedF[height][width], 0);
	fill(&visitedP[0][0], &visitedP[height][width], 0);
	while (!fire.empty()) {
		fire.pop();
	}
	while (!person.empty()) {
		person.pop();
	}
}

/// <summary>
/// 입력값 받는 함수
/// </summary>
void input() {
	
	int tc = 0;
	cin >> tc;
	for (int index = 0; index < tc; index++) {
		cin >> width >> height;
		init();
		for (int i = 0; i < height; i++) {
			for (int j = 0; j < width; j++) {
				cin>>building[i][j];
				//시작지점이면 상근 큐에 푸시
				if (building[i][j] == '@') {
					person.push({ i,j });
					//방문 했다고 체크
					visitedP[i][j] = 1;
				}
				//산불지점이면 불 큐에 푸시
				else if (building[i][j] == '*') {
					fire.push({i,j});
					//방문 했다고 체크
					visitedF[i][j] = 1;
				}
			}
		}
		solution();
	}
}

void solution() {
	//움직인 거리 
	int level = 1;
	while (!person.empty()) {
		//각 레벨에서 큐 사이즈만큼만 반복하기 위한 변수
		int qSize = person.size();
		int fSize = fire.size();
		//불 먼저 레벨 1만큼 진행
		for (int k = 0; k < fSize; k++) {
			pair<int, int> tmp = fire.front();
			fire.pop();
			for (int i = 0; i < 4; i++) {
				int nextA = tmp.first + dx[i];
				int nextB = tmp.second + dy[i];
				//다음 좌표가 범위 내에 있으면서, '.'이어야 이동 가능('*'이나 '@'는 신경안써도됨)
				if (nextA >= 0 && nextB >= 0 && nextA < height && nextB < width && (building[nextA][nextB] == '.')) {
					//방문안했다면
					if (!visitedF[nextA][nextB]) {
						//방문 체크
						visitedF[nextA][nextB] = 1;
						//큐에 해당 좌표 푸시
						fire.push({ nextA,nextB });
					}
				}
			}
		}
		//상근이 진행
		for (int i = 0; i < qSize; i++) {
			pair<int, int> tmp = person.front();
			person.pop();
			for (int i = 0; i < 4; i++) {
				int nextA = tmp.first + dx[i];
				int nextB = tmp.second + dy[i];
				//탈출할수 있다면
				if (nextA<0 || nextA==height|| nextB<0 ||nextB==width) {
					cout << level<<'\n';
					return;
				}
				//범위내에 있으면서, 다음 칸이 빈 공간이면서, 불길이 안닿은 곳이면
				if (nextA >= 0 && nextB >= 0 && nextA < height && nextB < width && building[nextA][nextB] == '.' && visitedF[nextA][nextB] != 1) {
					if (!visitedP[nextA][nextB]) {
						visitedP[nextA][nextB] = 1;
						person.push({ nextA,nextB });
					}
				}
			}
		}
		level++;
	}
    //반복문 빠져나오면 탈출을 못한 것이므로
	cout << "IMPOSSIBLE" << '\n';
}

int main() {
	input();
}

문풀후생

탈출 조건을

if (building[nextA][nextB]=='.' && visitedF[nextA][nextB] != 1 && (nextA == 0 || nextA == height - 1 || nextB == 0 || nextB == width - 1)) {
	//경계면에 도달햇으므로 탈출하려면 1만큼 더 증가시켜서 출력
	cout << level+1<<'\n';
	return;
	}

다음 칸에 경계면에 도달했고, 빈칸이라면('.') 탈출했으므로
level을 1만큼 증가시켜서 출력하는 방식으로 구현을 하였다.

하지만, @.. 이런식으로 출발하자마자 바로 탈출 할 수 있는 경우에서
바로 탈출이 아니라 빈칸으로 향해서 오답이 나왔다.

따라서,

	//탈출할수 있다면
	if (nextA<0 || nextA==height|| nextB<0 ||nextB==width) {
		cout << level<<'\n';
		return;
		}

범위밖으로 벗어났을 때, 출력하도록 변경하니 정답이 나왔다.