[백준][6593] 상범 빌딩

이 포스트는 백준 사이트의 상범 빌딩 문제 풀이입니다.

문제

해결 과정

이 문제는 BFS를 활용하면 쉽게 해결할 수 있습니다.

일반적인 최단거리 문제는 2차원 배열 혹은 그래프에서 구하는 형태였습니다.
그러나 이 문제는 3차원 배열의 형태에서 최단거리를 구해야하는 문제입니다.

따라서 이 문제를 구하기 위해 x축, y축에 z축을 더하여 3차원 배열에서 BFS를 실행하여
원하는 지점까지의 최단거리를 구하고자 하였습니다.

특정 지점에서 이동할 수 있는 방향은 총 6가지(상, 하, 동, 서, 남, 북)이므로
이를 dir_x, dir_y, dir_z 배열로 표현하고
BFS에서 사용할 방문 확인 배열도 3차원 배열로 선언하였습니다.

코드 구현

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct POINT{
    int x, y, z;

    bool operator==(const POINT& rhs) {
        if(this->x == rhs.x && this->y == rhs.y && this->z == rhs.z)
            return true;
        return false;
    }
};

int dir_x[6]{0, 0, -1, 1, 0, 0};
int dir_y[6]{-1, 1, 0, 0, 0, 0};
int dir_z[6]{0, 0, 0, 0, -1, 1};

int L, R, C;
POINT start, goal;

vector<vector<vector<bool>>> visited;

int get_escape_time() {
    queue<pair<POINT, int>> q;
    q.push({start, 0});

    while(false == q.empty()) {
        auto curr = q.front();
        q.pop();

        if(curr.first == goal) {
            return curr.second;
        }

        for(int dir = 0; dir < 6; ++dir) {
            int new_x = curr.first.x + dir_x[dir];
            int new_y = curr.first.y + dir_y[dir];
            int new_z = curr.first.z + dir_z[dir];

            if(new_x < 0 || new_x >= C || new_y < 0 || new_y >= R || new_z < 0 || new_z >= L)
                continue;
            if(visited[new_z][new_y][new_x])
                continue;

            visited[new_z][new_y][new_x] = true;
            q.push(make_pair(POINT{new_x, new_y, new_z}, curr.second + 1));
        }
    }

    return 0;
}

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

    while(true) {
        cin >> L >> R >> C;
        if(L == 0) break;

        visited.assign(L, vector<vector<bool>>(R, vector<bool>(C, false)));

        char info;
        for(int z = 0; z < L; ++z) {
            for(int y = 0; y < R; ++y) {
                for(int x = 0; x < C; ++x) {
                    cin >> info;

                    if(info == '#') {
                        visited[z][y][x] = true;
                    } else if(info == 'S') {
                        start = POINT{x, y, z};
                        visited[z][y][x] = true;
                    } else if(info == 'E') {
                        goal = POINT{x, y, z};
                    } else if(info == '.') {
                        visited[z][y][x] = false;
                    }
                }
            }
        }

        int time = get_escape_time();
        if(time == 0) {
            printf("Trapped!\n");
        } else {
            printf("Escaped in %d minute(s).\n", time);
        }
    }

    return 0;
}

실행 결과