BOJ 6593 - 상범 빌딩 링크
(2023.09.13 기준 G5)

문제

L×R×C 크기의 빌딩이 있다. 인접한 6개의 칸으로 이동할 때에는 1분이 걸리며, 대각석으로는 이동이 불가능하다. 각 칸은 지나갈 수 없는 칸, 빈칸, 시작 지점, 출구 중 하나이다.

시작 지점에서 출구까지의 최단 시간 출력

알고리즘

간선의 가중치가 전부 동일한 그래프에서의 최단 시간은 BFS

풀이

입력이 좀 난해할 수 있는데
이런 모양이라고 생각하면 된다.

여느 BFS 기본 문제처럼 시작 지점에서 BFS를 돌려 출구에 도착하는 최단 시간을 구하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef tuple<int, int, int> tiii;

const int MAXN = 30;
const tiii dir[6] = {{0, 0, 1}, {0, 0, -1}, {0, 1, 0}, {0, -1, 0}, {-1, 0, 0}, {1, 0, 0}}; // 동서남북상하

vector<string> matrix[MAXN];
int dist[MAXN][MAXN][MAXN];
deque<tiii> dq;

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

    int L, R, C, ei, ej, ek; cin >> L >> R >> C;
    for (; L; cin >> L >> R >> C){
        for (int i = 0; i < L; i++){
            matrix[i].resize(R);
            for (int j = 0; j < R; j++) cin >> matrix[i][j];
        }

        // 시작 지점을 찾아 dq에 넣고, 출구를 찾아 저장
        fill(&dist[0][0][0], &dist[L - 1][R - 1][C], -1); // -1은 아직 방문 전인 지점
        for (int i = 0; i < L; i++) for (int j = 0; j < R; j++) for (int k = 0; k < C; k++){
            if (matrix[i][j][k] == 'S'){
                dq.push_back({i, j, k});
                dist[i][j][k] = 0;
            }
            else if (matrix[i][j][k] == 'E') ei = i, ej = j, ek = k;
        }

        // 6방향을 따라 BFS
        while (!dq.empty()){
            auto [i, j, k] = dq.front(); dq.pop_front();
            for (auto [di, dj, dk]: dir)
                if (0 <= i + di && i + di < L && 0 <= j + dj && j + dj < R && 0 <= k + dk && k + dk < C && matrix[i + di][j + dj][k + dk] != '#' && !~dist[i + di][j + dj][k + dk]){
                    dq.push_back({i + di, j + dj, k + dk});
                    dist[i + di][j + dj][k + dk] = dist[i][j][k] + 1;
                }
        }

        if (~dist[ei][ej][ek]) cout << "Escaped in " << dist[ei][ej][ek] << " minute(s).\n";
        else cout << "Trapped!\n";
    }
}

• Python

import sys; input = sys.stdin.readline
from collections import deque

dir = [(0, 0, 1), (0, 0, -1), (0, 1, 0), (0, -1, 0), (-1, 0, 0), (1, 0, 0)] # 동서남북상하

while True:
    L, R, C = map(int, input().split())
    if not L:
        break

    matrix = [[] for _ in range(L)]
    for i in range(L):
        for _ in range(R):
            matrix[i].append(input().strip())
        input()

    # 시작 지점을 찾아 dq에 넣고, 출구를 찾아 저장
    dq = deque()
    dist = [[[-1] * C for _ in range(R)] for _ in range(L)] # -1은 아직 방문 전인 지점
    for i in range(L):
        for j in range(R):
            for k in range(C):
                if matrix[i][j][k] == 'S':
                    dq.append((i, j, k))
                    dist[i][j][k] = 0
                elif matrix[i][j][k] == 'E':
                    ei = i; ej = j; ek = k

    # 6방향을 따라 BFS
    while dq:
        i, j, k = dq.popleft()
        for di, dj, dk in dir:
            if 0 <= i + di < L and 0 <= j + dj < R and 0 <= k + dk < C and matrix[i + di][j + dj][k + dk] != '#' and not ~dist[i + di][j + dj][k + dk]:
                dq.append((i + di, j + dj, k + dk))
                dist[i + di][j + dj][k + dk] = dist[i][j][k] + 1

    print('Escaped in %d minute(s).' % dist[ei][ej][ek] if ~dist[ei][ej][ek] else 'Trapped!')