[백준/C++] 6593번 상범 빌딩

문제: www.acmicpc.net/problem/6593

6593번: 상범 빌딩

 

 

문제풀이

 

3차원에서 BFS 알고리즘으로 최단거리를 구하는 문제이다.

 

3차원 좌표를 표현하기 위해 tuple을 사용했다.

 

 

코드

#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

int dz[6] = {-1,1,0,0,0,0};
int dx[6] = {0,0,-1,1,0,0};
int dy[6] = {0,0,0,0,-1,1};

string board[30][30];
int dist[30][30][30];

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);

    while(true){
        int l,r,c;
        cin>>l>>r>>c;

        if(l==0 && r==0 && c==0) break;

        for(int h=0; h<l; h++){
            for(int i=0; i<r; i++){
                fill(dist[h][i], dist[h][i]+c, 0);
            }
        }

        queue<tuple<int,int,int>> q;
        for(int h=0; h<l; h++){
            for(int i=0; i<r; i++){
                cin>>board[h][i];
                for(int j=0; j<c; j++){
                    if(board[h][i][j] == 'S'){
                        q.push(make_tuple(h,i,j));
                        dist[h][i][j] = 1;
                    }
                }
            }
        }

        bool flag = false;

        while(!q.empty()){
            tuple<int,int,int> cur = q.front();
            q.pop();

            if(board[get<0>(cur)][get<1>(cur)][get<2>(cur)] == 'E'){
                cout<<"Escaped in "<<dist[get<0>(cur)][get<1>(cur)][get<2>(cur)]-1<<" minute(s).\n";
                flag = true;
                break;
            }

            for(int dir=0; dir<6; dir++){
                int nz = get<0>(cur) + dz[dir];
                int nx = get<1>(cur) + dx[dir];
                int ny = get<2>(cur) + dy[dir];

                if(nz<0||nz>=l||nx<0||nx>=r||ny<0||ny>=c) continue;
                if(dist[nz][nx][ny] || board[nz][nx][ny] == '#') continue;

                dist[nz][nx][ny] = dist[get<0>(cur)][get<1>(cur)][get<2>(cur)] + 1;
                q.push(make_tuple(nz,nx,ny));
            }
        }

        if(flag){
            while(!q.empty()) q.pop();
        }
        else{
            cout<<"Trapped!\n";
        }
    }

    return 0;
}

 

 

결과