[ 백준 BOJ ] 6593번 - 상범 빌딩 (C++)

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

생각 흐름

• 일반적인 BFS로 최단 시간을 찾는 문제이다.
• 특이한 점으로는 3차원이다.

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>

using namespace std;

int L, R, C;
vector<vector<string>> vvs;
bool checked[30][30][30];

int mz[6] = {0,0,0,0,1,-1};
int my[6] = {0,0,1,-1,0,0};
int mx[6] = {1,-1,0,0,0,0};

int bfs(int sz, int sy, int sx, int ez, int ey, int ex){
    checked[sz][sy][sx] = true;
    // minute, y, x
    queue<pair<int, pair<int, pair<int,int>>>> q;
    q.push({0,{sz,{sy,sx}}});
    
    while(!q.empty()){
        int minute = q.front().first;
        int z = q.front().second.first;
        int y = q.front().second.second.first;
        int x = q.front().second.second.second;
        q.pop();
        
        if(z==ez && y == ey && x == ex) return minute;
        
        for(int i = 0; i<6; i++){
            int dz = z+mz[i];
            int dy = y+my[i];
            int dx = x+mx[i];
            
            if(dz<0 || dz>=L || dy<0 || dy>=R || dx<0 || dx>=C) continue;
            if(checked[dz][dy][dx]) continue;
            if(vvs[dz][dy][dx]=='#') continue;
            
            checked[dz][dy][dx]=true;
            
            q.push({minute+1,{dz,{dy,dx}}});
        }
    }
    
    return -1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    while(true){
        cin>>L>>R>>C;
        if(L==R && R==C && C == 0) break;
        vvs.clear();
        memset(checked, false, sizeof(checked));
        
        int sz = -1, sy = -1, sx = -1, ez = -1, ey = -1, ex = -1;
        
        for(int i = 0; i<L; i++){
            vector<string> vs;
            for(int j = 0; j<R; j++){
                string tmp;
                cin>>tmp;
                
                for(int k = 0; k<C; k++){
                    if(tmp[k]=='S'){
                        sz = i;
                        sy = j;
                        sx = k;
                    }
                    if(tmp[k]=='E'){
                        ez = i;
                        ey = j;
                        ex = k;
                    }
                }
                
                vs.push_back(tmp);
            }
            vvs.push_back(vs);
        }
        
        int minute = bfs(sz, sy, sx, ez, ey, ex);
        if(minute == -1) cout<<"Trapped!"<<endl;
        else cout<<"Escaped in "<<minute<<" minute(s)."<<endl;
    }
    
    return 0;
}

그냥 bfs 돌리면 된다.. 특이한 것으로는 3차원..