[백준] 6593번 상범빌딩

 

[적용한 알고리즘]

BFS

 

[아이디어]

아주아주 기본적인 BFS 문제가 3차원으로 확장된거 정도?

 

[생각의 흐름 / 절차] 

갈 수 있는지 검사해주고 queue에 추가해주면 됨.

 

[교훈]

3차원이라 pair을 두번 쓸까 아님 구조체를 쓸까

고민했는데 앞으로 좌표 관련된건 구조체로 해주는게 좋을 듯 하다.

 

<코드>

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

typedef struct {
    int z;
    int x;
    int y;
} cord;

int dirx[] = {1, -1, 0, 0, 0, 0};
int diry[] = {0, 0, 1, -1, 0, 0};
int dirz[] = {0, 0, 0, 0, 1, -1};
int l, r, c;
char building[31][31][31];
bool visited[31][31][31];
int dist[31][31][31];
queue<cord> q;

void bfs(){
    while (!q.empty()){
        int curz = q.front().z;
        int curx = q.front().x;
        int cury = q.front().y;
        q.pop();

        for (int k = 0; k < 6; k++){
            int nx = curx + dirx[k];
            int ny = cury + diry[k];
            int nz = curz + dirz[k];

            if (0 <= nx && nx < r && 0 <= ny && ny < c && 0 <= nz && nz < l){
                if (!visited[nz][nx][ny] && building[nz][nx][ny] != '#'){
                    visited[nz][nx][ny] = true;
                    dist[nz][nx][ny] = dist[curz][curx][cury] + 1;
                    q.push({nz, nx, ny});
                }
            }
        }
    }
}

int main(){
    while (true){
        memset(building, 0, sizeof(building));
        memset(dist, 0, sizeof(dist));
        memset(visited, false, sizeof(visited));

        scanf("%d %d %d", &l, &r, &c);
        if (l == 0 && r == 0 && c == 0) break;

        int x, y, z; //z층 x행 y열
        int ex, ey, ez;

        for (int k = 0; k < l; k++){
            for (int i = 0; i < r; i++){
                scanf("%s", building[k][i]);
                for (int j = 0; j < c; j++){
                    if (building[k][i][j] == 'S'){
                        x = i;
                        y = j;
                        z = k;
                    }
                    if (building[k][i][j] == 'E'){
                        ex = i;
                        ey = j;
                        ez = k;
                    }
                }
            }
        }

        visited[z][x][y] = true;
        q.push({z, x, y});
        bfs();

        if (!visited[ez][ex][ey]){
            printf("Trapped!\n");
        }
        else {
            printf("Escaped in %d minute(s).\n", dist[ez][ex][ey]);
        }
    }

    return 0;
}