[백준 6593번] 상범 빌딩

문제 링크: https://www.acmicpc.net/problem/6593

6593번: 상범 빌딩

<문제 풀이> BFS

BFS로 dx, dy 방향으로 최단거리를 구하는 문제에서 dz 방향이 추가된 문제입니다. 

3차원 배열 입력과, dz방향 추가만 고려하면 구현하는 건 2차원과 동일합니다.

int dx[6] = { 0,0, 1, -1, 0, 0 }; //동 서 남 북 상 하

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

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

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
using namespace std;
 
int dx[6] = { 0,0, 1, -1, 0, 0 }; //동 서 남 북 상 하
int dy[6] = { 1,-1, 0, 0, 0 , 0 };
int dz[6] = { 0, 0, 0, 0 , 1, -1 };
 
char building[30][30][30];
int visited[30][30][30];
 
int L, R, C;
class pos {
public:
    int z;
    int x;
    int y;
    pos(int z, int x, int y) : z(z), x(x), y(y) {
    }
};
 
int bfs() {
    queue<pos> Q;
    for (int z = 0; z < L; z++) {
        for (int x = 0; x < R; x++) {
            for (int y = 0; y < C; y++) {
                if (building[z][x][y] == 'S') {
                    Q.push({ z, x, y });
                    visited[z][x][y] = 1;
                }
            }
        }
    }
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        if (building[cur.z][cur.x][cur.y] == 'E') { //Escaped
            return visited[cur.z][cur.x][cur.y] - 1;
        }
        for (int dir = 0; dir < 6; dir++) {
            int nz = cur.z + dz[dir];
            int nx = cur.x + dx[dir];
            int ny = cur.y + dy[dir];
            if (nx < 0 || ny < 0 || nz < 0 || nz >= L ||nx >= R || ny >= C ) continue;
            if (building[nz][nx][ny] == '#' || visited[nz][nx][ny]) continue;
            visited[nz][nx][ny] = visited[cur.z][cur.x][cur.y] + 1;
            Q.push({ nz, nx, ny });
        }
    }
    return -1; //Trapped!
}
 
void reset() {
    for (int z = 0; z < L; z++) {
        for (int x = 0; x < R; x++) {
            for (int y = 0; y < C; y++) {
                building[z][x][y] = 0;
                visited[z][x][y] = 0;
            }
        }
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
   
    while (true) {
        cin >> L >> R >> C;
        if (L == 0 && R == 0 && C == 0) break;
        for (int z = 0; z < L; z++) {
            for (int x = 0; x < R; x++) {
                for (int y = 0; y < C; y++) {
                    cin >> building[z][x][y];
                }
            }
        }
        int res = bfs();
        if (res == -1) {
            cout << "Trapped!\n";
        }
        else {
            cout << "Escaped in " << res << " minute(s).\n";
        }
        reset();
    }
    return 0;
}