백준 6593 c++ 상범빌딩 (정육면체)

백준 6593 - 상범빌딩

문제

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

 

 

 

답안 코드 : 

#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

int L, R, C;
char board[32][32][32];
int dist[32][32][32];

int dl[6] = {1, -1, 0, 0, 0, 0};
int dr[6] = {0, 0, 1, -1, 0, 0};
int dc[6] = {0, 0, 0, 0, 1, -1};

int main()
{
    FIO;
    while (true)
    {
        cin >> L >> R >> C;
        if (L == 0 && R == 0 && C == 0)
            break;

        for (int i = 0; i < L; i++)
        {
            for (int j = 0; j < R; j++)
            {
                fill(dist[i][j], dist[i][j] + C, 0);
            }
        }

        queue<tuple<int, int, int>> Q;

        for (int i = 0; i < L; i++)
        {
            for (int j = 0; j < R; j++)
            {
                for (int k = 0; k < C; k++)
                {
                    cin >> board[i][j][k];
                    if (board[i][j][k] == 'S')
                    {
                        Q.push({i, j, k});
                        dist[i][j][k] = 0;
                    }
                    else if (board[i][j][k] == '.' || board[i][j][k] == 'E')
                        dist[i][j][k] = -1;
                    else if (board[i][j][k] == '#')
                        dist[i][j][k] = -2;
                }
            }
        }

        int ans = -1;
        while (!Q.empty())
        {
            auto cur = Q.front();
            Q.pop();

            int curH, curX, curY;
            tie(curH, curX, curY) = cur;

            if (board[curH][curX][curY] == 'E')
            {
                ans = dist[curH][curX][curY];
                break;
            }

            for (int d = 0; d < 6; d++)
            {
                int nh = curH + dl[d];
                int nx = curX + dr[d];
                int ny = curY + dc[d];

                if (nh < 0 || nh >= L || nx < 0 || nx >= R || ny < 0 || ny >= C)
                    continue;
                if (board[nh][nx][ny] == '#')
                    continue;
                if (dist[nh][nx][ny] != -1)
                    continue;

                dist[nh][nx][ny] = dist[curH][curX][curY] + 1;
                Q.push({nh, nx, ny});
            }
        }

        if (ans == -1)
            cout << "Trapped!" << "\n";
        else
            cout << "Escaped in " << ans << " minute(s)." << "\n";
    }
    return 0;
}

 

생각 : 

이 문제를 풀기 위해 3차원 BFS를 활용한다. 각 위치에서 6방향(동, 서, 남, 북, 상, 하)으로 이동할 수 있으며, 최단 시간을 구하는 문제이므로 BFS가 적절하다. 

 

이 문제는 3차원 BFS를 활용한 전형적인 최단 거리 문제이다.

 

큐에서 원소를 꺼내는 코드

auto cur = Q.front();
Q.pop();

queue<tuple<int, int, int>> 형태의 큐에서 front()를 가져온 후 pop()을 수행한다.

auto를 사용하면 타입을 직접 명시할 필요 없이 자동으로 tuple<int, int, int>로 추론된다.

tie를 활용한 다중 변수 할당

int curH, curX, curY;
tie(curH, curX, curY) = cur;

tuple에서 값을 꺼내어 각각 curH, curX, curY 변수에 저장한다.

tie()를 활용하면 가독성이 좋고, 명시적으로 여러 변수를 초기화할 수 있다.

6방향 이동을 위한 배열 설정

int dl[6] = {1, -1, 0, 0, 0, 0};
int dr[6] = {0, 0, 1, -1, 0, 0};
int dc[6] = {0, 0, 0, 0, 1, -1};

dl, dr, dc 배열을 이용하면 코드에서 방향 이동을 직관적으로 표현할 수 있다. for문을 이용해 d 값을 0부터 5까지 증가시키면서 한 번에 탐색할 수 있도록 한다.

BFS 탐색 코드

for (int d = 0; d < 6; d++) {
    int nh = curH + dl[d];
    int nx = curX + dr[d];
    int ny = curY + dc[d];

    if (nh < 0 || nh >= L || nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
    if (board[nh][nx][ny] == '#') continue;
    if (dist[nh][nx][ny] != -1) continue;
    
    dist[nh][nx][ny] = dist[curH][curX][curY] + 1;
    Q.push({nh, nx, ny});
}

1. dl, dr, dc 배열을 사용해 6방향으로 이동을 시도한다.
2. 이동할 위치가 유효한 범위 내에 있는지 확인한다.
3. 이동할 위치가 벽('#')이 아니고, 방문하지 않은 곳인지 확인한다.
4. 이동한 위치의 dist 값을 현재 위치 +1로 갱신한다.
5. 새로운 위치를 큐에 넣어 탐색을 이어간다.

시간 복잡도 분석

BFS의 시간 복잡도는 O(L * R * C)이다. 최대 값이 30 * 30 * 30 = 27000이므로 충분히 처리할 수 있다.