[백준] 골드5 : (6593) 상범 빌딩

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

 

3차원 BFS로 풀었다.

각 위치에 대한 정보를 { 문자, 방문한 시간 }으로 잡았다.

처음으로 각 위치를 방문할 때, 방문한 시간을 저장한다.

그러면, 이후에 다른 queue에서 해당 위치를 방문했을 때, 서로 시간을 비교해서 더 짧은 시간을 두도록 했다.

bool로 하지 않은 이유는, 최종적으로 목적지에 도착했을 때의 시간을 알아야 하기에, 시간과 방문 체크를 동시에 가능하도록 하기 위해서 int로 했다.

#include <iostream>
#include <cstring>
#include <queue>
#include <tuple>
using namespace std;

// 동 서 남 북 상 하
int dx[]{ 1, -1, 0, 0, 0, 0 };
int dy[]{ 0, 0, 1, -1, 0, 0 };
int dz[]{ 0, 0, 0, 0, 1, -1 };

pair<char, int> Data[32][32][32];

int BFS(const tuple<int, int, int> Player)
{
	queue<int> qx, qy, qz, qn;
	qx.push(get<2>(Player)), qy.push(get<1>(Player)), qz.push(get<0>(Player)), qn.push(0);

	while (!qx.empty())
	{
		// 현재 위치
		int x = qx.front(), y = qy.front(), z = qz.front(), n = qn.front();
		qx.pop(), qy.pop(), qz.pop(), qn.pop();

		for (int i = 0; i < 6; ++i)
		{
			// 다음 이동 위치
			int nx = x + dx[i], ny = y + dy[i], nz = z + dz[i];

			// 0보다 작거나 & 범위를 벗어나거나 & 벽인 경우 패스
			if (nx < 0 || ny < 0 || nz < 0 || Data[nz][ny][nx].first == '#' || !Data[nz][ny][nx].first) continue;

			// 다음 이동 위치를 한 번 갔었는데, 그 비용이 더 싼 경우 패스
			if (Data[nz][ny][nx].second != 0 && Data[nz][ny][nx].second <= n + 1) continue;

			// 탈출구인경우 탈출
			if (Data[nz][ny][nx].first == 'E') return n + 1;

			Data[nz][ny][nx].second = n + 1;
			qx.push(nx), qy.push(ny), qz.push(nz), qn.push(n + 1);
		}
	}

	return 0;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int L, R, C;

	while (true)
	{
		cin >> L >> R >> C;
		if (!L && !R && !C) return 0;

		// 메모리 초기화
		memset(Data, 0, sizeof(Data));

		tuple<int, int, int> Player;
		for (int l = 0; l < L; ++l)
		{
			for (int r = 0; r < R; ++r)
			{
				for (int c = 0; c < C; ++c)
				{
					cin >> Data[l][r][c].first;
					if (Data[l][r][c].first == 'S') Player = { l, r, c };
				}
			}
		}

		int Answer = BFS(Player);

		if (Answer) cout << "Escaped in " << Answer << " minute(s)." << "\n";
		else cout << "Trapped!" << "\n";
	}
}