백준 6593번 상범 빌딩 // C++

문제

 

당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다.

당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마나 걸릴까?

입력

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 개의 정수 L, R, C로 시작한다. L(1 ≤ L ≤ 30)은 상범 빌딩의 층 수이다. R(1 ≤ R ≤ 30)과 C(1 ≤ C ≤ 30)는 상범 빌딩의 한 층의 행과 열의 개수를 나타낸다.

그 다음 각 줄이 C개의 문자로 이루어진 R개의 행이 L번 주어진다. 각 문자는 상범 빌딩의 한 칸을 나타낸다. 금으로 막혀있어 지나갈 수 없는 칸은 '#'으로 표현되고, 비어있는 칸은 '.'으로 표현된다. 당신의 시작 지점은 'S'로 표현되고, 탈출할 수 있는 출구는 'E'로 표현된다. 각 층 사이에는 빈 줄이 있으며, 입력의 끝은 L, R, C가 모두 0으로 표현된다.

출력

각 빌딩에 대해 한 줄씩 답을 출력한다. 만약 당신이 탈출할 수 있다면 다음과 같이 출력한다.

Escaped in x minute(s).

여기서 x는 상범 빌딩을 탈출하는 데에 필요한 최단 시간이다.

만일 탈출이 불가능하다면, 다음과 같이 출력한다.

Trapped!

 

---

 

풀이

 

BFS를 이용한 미로 탈출이 3차원으로 바뀐 문제이다.

 

S에서 시작하며, #인 경우는 벽이므로 해당 좌표로 이동하지 못한다.

 

E까지 가는 최소 시간을 구하면 된다.

 

---

 

코드

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

bool visit[31][31][31] = { false, };
char building[31][31][31];
int dir[6][3] = { {1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1} };

typedef struct _location {
	int x, y, z;
	int m;
}location;

void solve();
void input(int L, int R, int C);

queue<location> q;

int main() {
	solve();

	return 0;
}

void solve() {
	int L, R, C;

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

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

		memset(visit, false, sizeof(visit));

		input(L, R, C);

		bool escape = false;

		while (!q.empty()) {
			location cur = q.front();
			q.pop();

			if (building[cur.z][cur.y][cur.x] == 'E') {
				printf("Escaped in %d minute(s).\n", cur.m);
				escape = true;
				break;
			}

			for (int i = 0; i < 6; i++) {
				location next = cur;
				next.x += dir[i][0];
				next.y += dir[i][1];
				next.z += dir[i][2];
				next.m += 1;

				if (0 <= next.x && next.x < C && 0 <= next.y && next.y < R && 0 <= next.z && next.z < L) {
					if (building[next.z][next.y][next.x] != '#' && !visit[next.z][next.y][next.x]) {
						q.push(next);
						visit[next.z][next.y][next.x] = true;
					}
				}
			}
		}

		while (!q.empty()) {
			q.pop();
		}

		if (!escape)
			cout << "Trapped!\n";
	}
}

void input(int L, int R, int C) {
	location temp;

	for (int i = 0; i < L; i++) {
		for (int j = 0; j < R; j++) {
			cin >> building[i][j];

			for (int k = 0; k < C; k++) {
				if (building[i][j][k] == 'S') {
					temp.x = k;
					temp.y = j;
					temp.z = i;
					temp.m = 0;

					visit[i][j][k] = true;

					q.push(temp);
				}
			}
		}
	}
}