[백준] 상범 빌딩 (C++)

문제

 

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

---

풀이

이 문제는 3차원 공간의 빌딩에서  BFS를 이용하여 시작 지점부터 탈출 지점까지의 최단 거리를 구하는 방식으로 풀이했다.

 

최단 거리를 저장하기 위해 벽(#)을 -1, 길(.)을 -2로 변환하여 map에 저장했다.

시작 지점에서 BFS를 진행했으며, 같은 층에서는 상하좌우로 이동이 가능하고, 층 간에는 위아래로 이동할 수 있어 각 지점에서 총 6방향으로 탐색을 진행했다.

 

모든 탐색이 끝나고 도착 지점의 값이 -2이라면 Trapped! 출력, -2가 아니라면 Escaped in 도착지점 값 minute(s).을 출력한다.

 

#include<iostream>
#include<queue>

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

using namespace std;

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

int L, R, C;

int map[31][31][31];

pair<int, pair<int, int>> startPos;
pair<int, pair<int, int>> escapePos;
void BFS() {
	queue <pair<int, pair<int, int>>> q;

	q.push(startPos);
	map[startPos.first][startPos.second.first][startPos.second.second] = 0;

	while (!q.empty()) {
		pair<int, pair<int, int>> front = q.front();
		int curPosX = front.second.second;
		int curPosY = front.second.first;
		int curFloor = front.first;
		q.pop();

		for (int i = 0; i < 4; i++) { // 같은 층 동서남북 이동
			int moveY = curPosY + dy[i];
			int moveX = curPosX + dx[i];

			if (moveY < 0 || moveX < 0 || moveY >= R || moveX >= C)
				continue;

			if (map[curFloor][moveY][moveX] == -2 || map[curFloor][moveY][moveX] > map[curFloor][curPosY][curPosX] + 1) {
				map[curFloor][moveY][moveX] = map[curFloor][curPosY][curPosX] + 1;
				q.push({ curFloor, { moveY,moveX } });
			}
		}

		for (int i = 0; i < 2; i++) { // 층 간(상하) 이동
			int moveF = curFloor + dy[i];

			if (moveF < 0 || moveF >= L)
				continue;

			if (map[moveF][curPosY][curPosX] == -2 || map[moveF][curPosY][curPosX] > map[curFloor][curPosY][curPosX] + 1) {
				map[moveF][curPosY][curPosX] = map[curFloor][curPosY][curPosX] + 1;
				q.push({ moveF, { curPosY,curPosX } });
			}
		}
	}
}

int main() {

	while (true) {
		cin >> L >> R >> C;

		if (L == 0 && R == 0 && C == 0) {
			break;
		}

		char sel;
		for (int i = 0; i < L; i++) { // 입력 
			for (int j = 0; j < R; j++) {
				for (int k = 0; k < C; k++) {
					cin >> sel;
					if (sel == '#') {
						map[i][j][k] = -1;
					}
					else {
						map[i][j][k] = -2;
						if (sel == 'S') {
							startPos = { i, { j,k } };
						}
						else if (sel == 'E') {
							escapePos = { i, { j,k } };
						}
					}

				}
			}
		}

		BFS();

		if (map[escapePos.first][escapePos.second.first][escapePos.second.second] == -2) {
			cout << "Trapped!" << endl;
		}
		else {
			int count = map[escapePos.first][escapePos.second.first][escapePos.second.second];
			cout << "Escaped in " << count << " minute(s)." << endl;
		}
	}

	return 0;
}