728x90
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";
}
}
728x90
'📕알고리즘 문제 > 📝Baekjoon' 카테고리의 다른 글
| [백준] 실버1 : (16198) 에너지 모으기 (0) | 2025.08.21 |
|---|---|
| [백준] 골드5 : (11509) 풍선 맞추기 (0) | 2025.08.15 |
| [백준] 골드4 : (24391) 귀찮은 해강이 (0) | 2025.07.31 |
| [백준] 골드5 : (2668) 숫자고르기 (0) | 2025.07.11 |
| [백준] 골드4 : (3584) 가장 가까운 공통 조상 (0) | 2025.05.24 |