[백준 6593번 상범 빌딩] 문제 풀이

문제 사이트 : https://www.acmicpc.net/problem/6593

 

문제

당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다.

당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마나 걸릴까?

입력

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 개의 정수 L, R, C로 시작한다. L(1 ≤ L ≤ 30)은 상범 빌딩의 층 수이다. R(1 ≤ R ≤ 30)과 C(1 ≤ C ≤ 30)는 상범 빌딩의 한 층의 행과 열의 개수를 나타낸다.

그 다음 각 줄이 C개의 문자로 이루어진 R개의 행이 L번 주어진다. 각 문자는 상범 빌딩의 한 칸을 나타낸다. 금으로 막혀있어 지나갈 수 없는 칸은 '#'으로 표현되고, 비어있는 칸은 '.'으로 표현된다. 당신의 시작 지점은 'S'로 표현되고, 탈출할 수 있는 출구는 'E'로 표현된다. 각 층 사이에는 빈 줄이 있으며, 입력의 끝은 L, R, C가 모두 0으로 표현된다. 시작 지점과 출구는 항상 하나만 있다.

출력

각 빌딩에 대해 한 줄씩 답을 출력한다. 만약 당신이 탈출할 수 있다면 다음과 같이 출력한다.

Escaped in x minute(s).

여기서 x는 상범 빌딩을 탈출하는 데에 필요한 최단 시간이다.

만일 탈출이 불가능하다면, 다음과 같이 출력한다.

Trapped!

 

- 해결 아이디어

• 큐를 이용해서 BFS 구현
• 거리 배열을 따로 만들어서 각 지점까지의 최소 거리를 저장

- 해결 방법

1. 처음에 시작 위치를 큐에 삽입

2. 큐를 pop해서 현재 위치를 가져옴.

3. 현재 위치 + 6가지 방향으로 이동했을 때 위치가 비어있는 칸 또는 탈출구 안에 있고, 방문하지 않은 칸(동일한 지점을 방문하더라도 이후에 진행된 요소들은 무조건 해당 지점의 최소 이동 횟수보다 크거나 같기 때문에 대소 비교를 하지 X)이라면 큐에 삽입하고 거리 배열 요소에 현재 위치의 최소 이동 횟수 + 1을 저장 

4. 2,3번 과정을 반복하다가

최종 위치에 방문한다면 탈출구 위치의 최소 거리를 반환

큐가 빌때까지 최종 위치에 방문하지 못한다면 실패의 의미로 -1를 반환

 

* 백준 7562번 나이트의 이동 문제와 해결 방법이 3차원 배열과 이동 방법이 다르다는 점 빼고는 거의 유사함.

https://chakae.tistory.com/10

[백준 7562번 나이트의 이동] 문제풀이

 

- 정답 코드 (C++)

// 백준 문제 : 상범 빌딩
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <tuple>

using namespace std;

int dz[6] = {-1,1,0,0,0,0}; // 위, 아래, 앞, 오, 뒤, 좌 순서
int dy[6] = {0,0,-1,0,1,0};
int dx[6] = {0,0,0,1,0,-1};
vector<int> L,R,C;

int bfs(int i, vector<vector<vector<char>>> building){
    queue<tuple<int,int,int>> qu;
    vector<vector<vector<int>>> dis(30,vector<vector<int>>(30,vector<int>(30,0))); 
    for(int j=0;j<L[i];j++){
        for(int z=0;z<R[i];z++){
            for(int q=0;q<C[i];q++){
                if(building[j][z][q] == 'S'){
                    qu.push({j,z,q});
                }
            }
        }
    }
    while(!qu.empty()){
        auto cur = qu.front(); qu.pop();
        int z = get<0>(cur);
        int y = get<1>(cur);
        int x = get<2>(cur);
        if(building[z][y][x] == 'E'){
            return dis[z][y][x];
        }
        for(int j=0;j<6;j++){
            int cz = z+dz[j];
            int cy = y+dy[j];
            int cx = x+dx[j];
            if(cz >= 0 && cz < L[i] && cy >= 0 && cy < R[i] && cx >= 0 && cx < C[i] && (building[cz][cy][cx] == '.' || building[cz][cy][cx] == 'E') && dis[cz][cy][cx] == 0){
                qu.push({cz,cy,cx});
                dis[cz][cy][cx] = dis[z][y][x] + 1;
                // cout << "============" << endl;
                // for(int z=0;z<L[i];z++){
                //     for(int q=0;q<R[i];q++){
                //         for(int w=0;w<C[i];w++){
                //             cout << dis[z][q][w];
                //         }
                //         cout << endl;
                //     }
                //     cout << "--------" << endl;
                // }
            }
        }
    }
    return -1;

}

int main(){
    int a,b,c;
    int count = 0;
    vector<vector<vector<vector<char>>>> building;
    cin >> a >> b >> c;
    while(a != 0 || b != 0 || c != 0){
        
        L.push_back(a);
        R.push_back(b);
        C.push_back(c);

        vector<vector<vector<char>>> d(30,vector<vector<char>>(30,vector<char>(30,'.')));
        for(int i=0;i<L[count];i++){
            for(int j=0;j<R[count];j++){
                string str;
                cin >> str;
                for(int z=0;z<C[count];z++){
                    d[i][j][z] = str[z];
                }
            }
        }
        building.push_back(d);

        // for(int i=0;i<L[count];i++){
        //     for(int j=0;j<R[count];j++){
        //         for(int z=0;z<C[count];z++){
        //             cout << d[i][j][z];
        //         }
        //         cout << endl;
        //     }
        //     cout << endl;
        // }

        cin >> a >> b >> c;
        count++;
    } 

    for(int i=0;i<count;i++){
        int result = bfs(i,building[i]);
        if(result == -1){
            cout << "Trapped!" << endl;
        } else {
            cout << "Escaped in " << result << " minute(s)." << endl;
        }
    }
}