[백준] 상범 빌딩

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

6593번: 상범 빌딩

우선 문제부터 간단하게 요약하면, 

 

3차원 공간에서 최단 시간에 탈출한다면 몇초가 걸리는지, 혹은 탈출이 불가능 하다면 trapped되었다고 출력해야 하는 것이 목표입니다.

 

<Solution>

기본적인 bfs의 구성을 단지 3차원으로 확장한 것입니다.

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <cstring>
#include <queue>
 
using namespace std;
 
#define MAX_SIZE (30)
int ans;
int L, R, C;
int d_l[] = {-1, 1, 0, 0, 0, 0};
int d_r[] = {0, 0, 1, -1, 0, 0};
int d_c[] = {0, 0, 0, 0, 1, -1};
 
struct pos{
    int l, r, c;
    int time;
};
 
 
char map[MAX_SIZE+10][MAX_SIZE+10][MAX_SIZE+10];
bool InputData(){
    // initialize map
    memset(map, 0, sizeof(map));
 
    cin >> L >> R >> C;
    if ((L == 0) && (R == 0) && (C == 0)) return false;
    for (int l=1; l<=L;l++){
        for (int r=1; r<=R; r++){
            cin >> &map[l][r][1];
        }
    }
    return true;
}
 
void solution(){
 
    // bfs
    queue <pos> q;
    pos init;
 
    for(int i = 1; i<=L; i++){
        for(int j = 1; j<=R; j++){
            for(int k = 1; k<=C; k++){
                if(map[i][j][k] == 'S'){
                    init.l = i;
                    init.r = j;
                    init.c = k;
                    init.time = 0;
                    map[i][j][k] = 'v'; // visited 표시
                }
            }
        }
    }
 
    q.push(init);
 
    while(!q.empty()){
        // print map
        // cout << "##################################" << endl;
        // for(int i = 1; i<=L; i++){
        //     for(int j = 1; j<=R; j++){
        //         cout << &map[i][j][1] << endl;
        //     }
        //     cout << endl;
        // }
 
 
        pos cur = q.front(); q.pop();
 
        for(int i = 0; i<6; i++){
            pos next;
            next.l = cur.l + d_l[i];
            next.r = cur.r + d_r[i];
            next.c = cur.c + d_c[i];
            next.time = cur.time+1;
             
            // if 도착지
            if(map[next.l][next.r][next.c] == 'E'){
                ans = next.time;
                break;
            }
            // 방문했거나, 금이거나 하면 진행 x
            if(map[next.l][next.r][next.c] != '.') continue;
            map[next.l][next.r][next.c] = 'v';
            q.push(next);
        }
 
    }
 
}
 
int main(){
 
    while(InputData()){
 
        ans = -1;
        solution();
 
        if (ans == -1) cout << "Trapped!" << endl;
        else cout << "Escaped in " << ans << " minute(s)." << endl;
    }
    return 0;
}