백준 6593번: 상범 빌딩

백준 6593번: 상범 빌딩

6593번: 상범 빌딩

 

탈출에 성공하면 탈출시간을 출력하고 아니면 "Trapped!"를 출력한다. 왠지 스타워즈가 생각나는 문제였다.

 

1트! BFS로 풀수 있는 간단한 문제였다. 3차원이기 때문에 인덱스 위치만 헷갈리지 않으면 되는 것 같다.

동서남북상하로 이동할 때 벽('#')으로만 이동하지 않게하고 출구지점('E')에 도달했을 때 BFS 함수를 종료하고

탈출 시간을 나타나게 했다. 출구에 도달하지 못할 시엔 -1을 리턴하여 출력시 Trapped!를 출력하게했다.

그리고 L, R, C가 모두 0이여야 반복문을 종료하기 때문에 항상 반복문을 시작할때는 큐에 있는 값을 제거하고 방문여부를 false로 초기화 시켜주어야하는 것만 조심하면 풀 수 있는 문제다.

 

#include<iostream>
#include<queue>
#include<cstring>
#define HIGH_FLOOR 31
using namespace std;

typedef struct escape{
    int d;
    int h;
    int w;
    int dist;
}escape;

int L, R, C;
char building[HIGH_FLOOR][HIGH_FLOOR][HIGH_FLOOR];
bool visit[HIGH_FLOOR][HIGH_FLOOR][HIGH_FLOOR];
queue<escape> q;
void init(){
    while(!q.empty()) q.pop();
    memset(visit, false, sizeof(visit));
}
int bfs(){
    int dirD[] = {1,-1,0,0,0,0};
    int dirH[] = {0,0,1,-1,0,0};
    int dirW[] = {0,0,0,0,1,-1};
    int d, h, w, dist;
    int dd, dh, dw;
    while(!q.empty()){
        d = q.front().d;
        h = q.front().h;
        w = q.front().w;
        dist = q.front().dist;
        q.pop();
        if(building[d][h][w] == 'E') return dist;
        for(int i = 0; i < 6; i++){
            dd = d + dirD[i];
            dh = h + dirH[i];
            dw = w + dirW[i];
            if(dd < 0 || dd >= L || dh < 0 || dh >= R || dw < 0 || dw >= C) continue;
            if(building[dd][dh][dw] == '#' || visit[dd][dh][dw]) continue;
            visit[dd][dh][dw] = true;
            q.push({dd, dh, dw, dist+1});
        }
    }
    return -1;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int res = -1;
    while(true){
        init();
        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++){
                for(int k = 0; k < C; k++){
                    cin >> building[i][j][k];
                    if(building[i][j][k] == 'S'){
                        q.push({d:i, h:j, w:k, dist:0});
                    }
                }
            }
        }
        res = bfs();
        if(res == -1) cout << "Trapped!\n";
        else cout << "Escaped in " << res << " minute(s).\n";
    }
    return 0;
}