상범 빌딩 6593

문제

접근 방법

3차원 BFS로 풀면 된다.
S에 위치를 큐에 저장하여 시작점으로 삼으면 된다.
BFS의 경우 가장 먼저 도달한 것이 최단 시간이다. (선입선출이기 때문이다)

코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int dx[] = {1, -1, 0, 0, 0, 0}, dy[] = {0, 0, 1, -1, 0, 0}, dz[] = {0, 0, 0, 0, 1, -1};
struct node
{
    int z, y, x, time;
};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    char map[31][31][31];
    int L, R, C;
    queue<node> bfs;
    while (true)
    {
        int time = -1;
        bfs = queue<node>();
        cin >> L >> R >> C;
        if (!L && !R && !C)
            break;
        for (int i = 0; i < L; ++i)
            for (int j = 0; j < R; ++j)
                for (int k = 0; k < C; ++k)
                {
                    char c;
                    cin >> c;
                    map[i][j][k] = c;
                    if (c == 'S')
                    {
                        map[i][j][k] = '#';
                        bfs.push({i, j, k, 0});
                    }
                }
        while (!bfs.empty())
        {
            node cur = bfs.front();
            bfs.pop();
            for (int i = 0; i < 6; ++i)
            {
                node next = {cur.z + dz[i], cur.y + dy[i], cur.x + dx[i], cur.time + 1};
                if (next.x < 0 || next.y < 0 || next.z < 0 || next.x >= C || next.y >= R || next.z >= L || map[next.z][next.y][next.x] == '#')
                    continue;
                if (map[next.z][next.y][next.x] == 'E')
                {
                    time = next.time;
                    break;
                }
                else
                {
                    map[next.z][next.y][next.x] = '#';
                    bfs.push(next);
                }
            }
        }
        if (time == -1)
        {
            cout << "Trapped!";
        }
        else
        {
            cout << "Escaped in " << time << " minute(s).";
        }
        cout << "\n";
    }
}

풀이

이미 지나간 곳은 #으로 설정해주어 못 돌아가게 해준다.
E에 도착하면 중지하고 출력해주면 된다.