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

문제

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

6593번: 상범 빌딩

풀이 방법

3차원 공간을 탐색해 시작지부터 목적지까지의 거리를 구하는 문제이다. 인접한 노드를 차례로 방문해 각 노드의 시작점까지의 거리를 구할 수 있는 BFS(너비 우선 탐색)을 사용해서 푼다. 탐색하면서 거리 배열을 갱신시켜주고, 탈출에 성공했을경우 목적지까지의 거리를 출력하면 된다.

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <tuple>
#include <cstring>
using namespace std;
int dz[] = {0,0,0,0,-1,1};
int dy[] = {-1,0,0,1,0,0};
int dx[] = {0,-1,1,0,0,0};
int main()
{
    while(true)
    {
        int L,R,C;
        scanf("%d %d %d\n", &L, &R, &C);
        if(L==0 && R==0 && C==0) break;
        char building[31][31][31];
        int dist[31][31][31];
        int startZ, startY, startX;
        int destZ, destY, destX;
        for(int i=0; i<L; i++)
        {
            for(int j=0; j<R; j++)
            {
                for(int k=0; k<C; k++)
                {
                    scanf("%c ", &building[i][j][k]);
                    if(building[i][j][k] == 'S')
                    {
                        startZ = i;
                        startY = j;
                        startX = k;
                    }
                    else if(building[i][j][k] == 'E')
                    {
                        destZ = i;
                        destY = j;
                        destX = k;
                    }
                }
                scanf("\n");
            }
            scanf("\n");
        }
        bool escape = false;
        memset(dist, 0, sizeof(dist));
        dist[startZ][startY][startX] = 0;
        queue<tuple<int,int,int>> q;
        q.push({startZ, startY, startX});
        while(!q.empty())
        {
            auto t = q.front();
            q.pop();
            int z = get<0>(t);
            int y = get<1>(t);
            int x = get<2>(t);
            if(z == destZ && y == destY && x == destX)
            {
                escape = true;
                break;
            }
            for(int i=0; i<6; i++)
            {
                int nz = z + dz[i];
                int ny = y + dy[i];
                int nx = x + dx[i];
                if(0<=nz && nz<L && 0<=ny && ny<R && 0<=nx && nx<C)
                {
                    if(dist[nz][ny][nx] == 0)
                    {
                    	if(building[nz][ny][nx] == '.' || building[nz][ny][nx] == 'E')
	                	{
		                    q.push({nz,ny,nx});
		                    dist[nz][ny][nx] = dist[z][y][x] + 1;
                    	}
                    }
                }
            }
        }
        if(escape) 
        	printf("Escaped in %d minute(s).\n", dist[destZ][destY][destX]);
        else 
        	printf("Trapped!\n");
    }
    return 0;
}

고찰

3차원이지만 2차원과 거의 동일해서 쉽게 풀 수 있는 문제이다. 다만 C-style 배열 선언이 편해서 사용했는데, 거리 배열을 초기화를 해주지 않으면 제대로 풀리지 않는 문제가 있다.

memset이나 선언 시 int dist[31][31][31] = {0,}; 처럼 초기화를 해줘야한다. 또, 연속된 문자 입력을 받을 때 개행 문자까지 같이 scanf로 들어오는 것도 주의해야한다.