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

문제

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

 

3차원 개념을 활용해서 푸는거라 문제 이해가 처음에는 좀 어려웠지만 문제는 쉬운 편.

 

풀이

 

입력을 받을 때, S와 E의 좌표를 저장해준다.

• 시작 좌표는 탐색 시작을 위해 사용한다.
• 목표 좌표는 출력에 사용한다.

이번 문제는 2차원 배열에서 ‘면'의 개념을 추가한 3차원으로 탐색을 해야 한다.

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

 

최소 이동 거리 저장 및 재방문 확인을 위한 배열을 만들어 주었다.

#define MAX 31

int visited[MAX][MAX][MAX]; // 최소 이동 거리

 

 

각 l, r, c의 범위에 유의하며 BFS로 탐색하여 풀면 된다.

 

소스

#include <iostream>
#include <queue>
#include <vector>
#include <memory.h>
#define MAX 31
 
int L, R, C;
char map[MAX][MAX][MAX];
int visited[MAX][MAX][MAX];
 
int dx[6] = {1, -1, 0, 0, 0, 0};
int dy[6] = {0, 0, -1, 1, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};
 
bool isValid(int x, int y, int z)
{
    if(x>L || y>R || z>C)
        return false;
    else if (x<0 || y<0 || z<0)
        return false;
    
    return true;
}
 
void BFS(int _l, int _r, int _c)
{
    std::queue<std::vector<int>> q;
    q.push(std::vector<int>({_l, _r, _c}));
    visited[_l][_r][_c] = 1;
   
    while(!q.empty())
    {
        int l = q.front()[0];
        int r = q.front()[1];
        int c = q.front()[2];
        q.pop();
        
        for(int i=0; i<6; ++i)
        {
            int x = l + dx[i];
            int y = r + dy[i];
            int z = c + dz[i];
 
            if(!isValid(x, y, z) || visited[x][y][z] > 0)
                continue;
            
            if(map[x][y][z] == 'E')
            {
                visited[x][y][z] = visited[l][r][c];
                return;
            }
            
            if(map[x][y][z] =='.')
            {
                q.push(std::vector<int>({x, y, z}));
                visited[x][y][z] = visited[l][r][c] + 1;
            }
        }
    }
    
}
int main()
{
    while(1)
    {
        int x=0, y=0, z = 0; //S
        int xx=0, yy=0, zz= 0; // E
        
        std::cin >> L >> R >> C;
        if(L==0 && R==0 && C==0)
            break;
 
        //initialize
        memset(map, NULL, sizeof(map));
        memset(visited, 0, sizeof(visited));
        
        for(int i=0; i<L; ++i){
            for(int j=0; j<R; ++j){
                for(int k=0; k<C; ++k)
                {
                    std::cin >> map[i][j][k];
                    if(map[i][j][k] == 'S')
                    {
                        x=i; y=j; z=k;
                    }
                    else if(map[i][j][k]=='E')
                    {
                        xx=i; yy=j; zz=k;
                    }
                        
                }
            }
        }
        
        //solve
        BFS(x, y, z);
        
        //output
        if(visited[xx][yy][zz]==0)
            std::cout << "Trapped!\n";
        else
            std::cout <<"Escaped in "<< visited[xx][yy][zz] << " minute(s).\n";
    }
    
    return 0;
}