상범 빌딩 //6593

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

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

• 출력
  

// Created by dongwan-kim on 2022/08/23.
#include<iostream>
#include<queue>
#include<algorithm>

#define MAX 31
using namespace std;

int l, r, c, map[MAX][MAX][MAX], escapeZ, escapeX, escapeY;
char graph[MAX][MAX][MAX];
bool visit[MAX][MAX][MAX];
queue<pair<int, pair<int, int>>> q;

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

void bfs() {
    while (!q.empty()) {
        int z = q.front().first;
        int x = q.front().second.first;
        int y = q.front().second.second;
        q.pop();
        for (int i = 0; i < 6; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int nz = z + dz[i];
            if (nx >= 0 && ny >= 0 && nz >= 0 && nz < l && nx < r && ny < c && graph[nz][nx][ny] != '#' &&
                !visit[nz][nx][ny]) {
                visit[nz][nx][ny] = true;
                map[nz][nx][ny] = map[z][x][y] + 1;
                q.push({nz, {nx, ny}});
            }
        }
    }
}


void reset() {
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < r; j++) {
            for (int k = 0; k < c; k++) {
                visit[i][j][k] = false;
                map[i][j][k] = 0;
            }
        }
    }

}


int main() {
    while (1) {
        cin >> l >> r >> c;
        if (l == 0 && r == 0 && c == 0)
            return 0;

        for (int i = 0; i < l; i++) {
            for (int j = 0; j < r; j++) {
                for (int k = 0; k < c; k++) {
                    cin >> graph[i][j][k];
                    if (graph[i][j][k] == 'S') {	//시작점 q에 push
                        q.push({i, {j, k}});
                        visit[i][j][k] = true;
                    }
                    if (graph[i][j][k] == 'E') {	//출구 좌표를 저장
                        escapeZ = i;
                        escapeX = j;
                        escapeY = k;
                    }
                }
            }
        }
        bfs();
        if (visit[escapeZ][escapeX][escapeY])
            cout << "Escaped in " << map[escapeZ][escapeX][escapeY] << " minute(s).\n";
        else
            cout << "Trapped!" << "\n";
        reset();
    }
}

풀이

건물을 탈출하는 최단시간을 구하는 문제이므로 BFS를 사용해 해결했다.

많이 보이는 그래프 최단거리 or 최단시간을 구하는 문제인데 차이점은 X,Y좌표로 푸는 2차원이 아닌 3차원으로 풀어야하는 문제이다. 동,서,남,북,상,하로 이동하기 때문에 이에 맞춰서 dx,dy,dz를 선언해 주었다.

입력 받을 때 시작점 'S'가 들어오면 q에 push해주고, 출구 'E'가 나오면 escapeX,Y,Z에 저장해 주었다. BFS를 돌면서 map배열에 막혀있지 않은 좌표까지 도착하는데 걸리는 최단 시간을 모두 담아준다.
BFS를 돈 후에 출구 좌표가 visit된 상태라면 출력해주고 !visit상태라면 "Trapped!"를 출력해준다.