BOJ 6593 · 상범 빌딩

알고리즘 분류 : BFS  

BFS를 통해 최단 탈출 시간을 구하는 문제다. 상범 빌딩에 갇힌 사람을 빌딩 밖으로 탈출시켜야 한다. 시작점은 'S'로 주어지고, 탈출구는 'E'로 주어진다. 3차원 배열을 선언하여 빌딩의 정보를 입력받고, 이동 거리를 저장할 dist 배열을 3차원으로 선언하고 방문 체크 용도로 사용한다.

• 입력받을 때 시작점의 위치와 도착점의 위치를 저장해두어야 한다.
• 이동은 인접한 '동서남북상하'로 한 칸씩만 이동할 수 있다.
• 이동할 때 빌딩의 범위를 벗어나는지 확인해야 한다.
• 벽(#)으로 이동할 수 없다.
• 탈출구에 도착하면 "Escaped in x minute(s)."를 출력한다. 탈출구에 도달하지 못하면 "Trapped!"를 출력한다.
• 여러 개의 테스트케이스가 주어지므로, 변수 초기화에 유의한다. 0 0 0이 입력되면 종료한다.

---

C++ 소스코드

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

struct building {
    int x, y, z;
};

int L, R, C;
int sx, sy, sz, ex, ey, ez;
char a[30][30][30];
int dist[30][30][30];
const int dx[] = {-1, 1, 0, 0, 0, 0};
const int dy[] = {0, 0, -1, 1, 0, 0};
const int dz[] = {0, 0, 0, 0, -1, 1};

void bfs() {
    queue<building> q;
    q.push({sx, sy, sz});
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y, z = q.front().z;
        q.pop();
        if (x == ex && y == ey && z == ez) {
            printf("Escaped in %d minute(s).\n", dist[x][y][z]);
            return;
        }
        for (int i=0; i<6; i++) {
            int nx = x+dx[i], ny = y+dy[i], nz = z+dz[i];
            if (nx < 0 || nx >= L || ny < 0 || ny >= R || nz < 0 || nz >= C) continue;
            if (dist[nx][ny][nz] || a[nx][ny][nz] == '#') continue;
            dist[nx][ny][nz] = dist[x][y][z] + 1;
            q.push({nx, ny, nz});
        }
    }
    printf("Trapped!\n");
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    while (true) {
        cin >> L >> R >> C;
        if (L == 0) break;
        memset(dist, 0, sizeof(dist));
        for (int i=0; i<L; i++) {
            for (int j=0; j<R; j++) {
                for (int k=0; k<C; k++) {
                    cin >> a[i][j][k];
                    if (a[i][j][k] == 'S') sx = i, sy = j, sz = k;
                    else if (a[i][j][k] == 'E') ex = i, ey = j, ez = k;
                }
            }
        }
        bfs();
    }
    return 0;
}

---

Python 3 소스코드

from collections import deque
from sys import stdin, stdout
input = stdin.readline
print = stdout.write

dx, dy, dz = (-1, 1, 0, 0, 0, 0), (0, 0, -1, 1, 0, 0), (0, 0, 0, 0, -1, 1)
L, R, C, sx, sy, sz, ex, ey, ez = [0]*9

def bfs(a, dist):
    q = deque()
    q.append((sx, sy, sz))
    while q:
        x, y, z = q.popleft()
        if x == ex and y == ey and z == ez:
            print("Escaped in %d minute(s).\n" % dist[x][y][z])
            return
        for i in range(6):
            nx, ny, nz = x+dx[i], y+dy[i], z+dz[i]
            if nx < 0 or nx >= L or ny < 0 or ny >= R or nz < 0 or nz >= C:
                continue
            if dist[nx][ny][nz] or a[nx][ny][nz] == '#':
                continue
            dist[nx][ny][nz] = dist[x][y][z] + 1
            q.append((nx, ny, nz))
    print("Trapped!\n")

while True:
    L, R, C = map(int, input().split())
    if L is 0:
        break
    a = [[[]*C for _ in range(R)] for _ in range(L)]
    dist = [[[0]*C for _ in range(R)] for _ in range(L)]
    for i in range(L):
        a[i] = [list(input().strip()) for _ in range(R)]
        input()
    for i in range(L):
        for j in range(R):
            for k in range(C):
                if a[i][j][k] == 'S':
                    sx, sy, sz = i, j, k
                elif a[i][j][k] == 'E':
                    ex, ey, ez = i, j, k
    bfs(a, dist)

---

참고

• 백준 온라인 저지 : BOJ 6593