백준 6593 상범빌딩 c++ [컴공과고씨]

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

6593번: 상범 빌딩

이 문제는 일반 탐색문제와 거의 흡사하지만 고려해주어야 할게 하나 더 추가된 형식이다. 바로 층 수가 있다는 것이다. 보통 탐색 문제의 경우 상하좌우만 움직여 좌표를 2개만 설정해주지만 이 문제 같은 경우 층 수도 고려를 해주어야 하기 때문에 층을 고려하는 좌표를 하나 추가해주어 풀어주면 간단히 해결된다.  나는 bfs를 이용하여 큐에 x,y,z,count를 튜플로 만들어 넣어주어 문제를 해결하였다. bfs 구현 같은 경우 dx,dy,dz를 이용하여 6개의 이동을 표현해 주었고 만약 탈출을 하지 못한경우 found 변수로 false를 주어 결과 벡터에 -1로 저장후 if문을 통해 trapped을 출력하게 만들었다. 탈출을 했을 경우 found를 true로 만들어주고 count값을 결과 벡터에 넣어주었다.

 

전체코드

#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
#include <string.h>
using namespace std;
int l, r, c;
char building[31][31][31];
bool visit[31][31][31];
int dx[] = {1,-1,0,0,0,0}; // 동서남북상하
int dy[] = {0,0,-1,1,0,0};
int dz[] = {0,0,0,0,1,-1};
vector<int> result;
bool found = false;
void bfs(int x1, int y1,int z1, int c1){
    queue<tuple<int, int, int, int>> q;
    q.push(make_tuple(x1, y1, z1, c1));
    visit[z1][y1][x1] = true;
    
    while(!q.empty()){
        int x = get<0>(q.front());
        int y = get<1>(q.front());
        int z = get<2>(q.front());
        int cnt = get<3>(q.front());
        if(building[z][y][x]=='E'){
            found = true;  
            result.push_back(cnt);
            break; // 탈출 했을 경우
        }
        q.pop();
        
        for (int i = 0; i < 6;i++){
            int n_x = x + dx[i];
            int n_y = y + dy[i];
            int n_z = z + dz[i];
 
            if (n_x >= 0 && n_y >= 0 && n_z >= 0 && n_x < c && n_y < r && n_z < l){
                if(!visit[n_z][n_y][n_x] && building[n_z][n_y][n_x]!='#'){
                    q.push(make_tuple(n_x, n_y, n_z,cnt+1));
                    visit[n_z][n_y][n_x] = true;
                } 
            }
        }
    }
}
int main(){
    while(1){
        cin >> l >> r >> c;
        if (l == 0 && r == 0 && c == 0){
            break; // 000이 들어오면 종료
        }
        int start_x, start_y, start_z;
        memset(visit, false, sizeof(visit));
        found = false;
 
        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'){
                        start_x = k;
                        start_y = j;
                        start_z = i; //시작 좌표 저장
                    }
                }
            }
        }
        bfs(start_x, start_y, start_z, 0);
        if(!found){ // 탈출을 못했을 경우 
            result.push_back(-1);
        }
    }
    for (int i = 0; i < result.size();i++){
        if(result[i] == -1){
            cout << "Trapped!" << '\n';
        }
        else{
            cout << "Escaped in " << result[i] << " minute(s)." << '\n';
        }
    }
 
    return 0;
}

사용 문법 : bfs, tuple

 

yea!