BOJ 6593 상범빌딩

디버깅 15분 포함 약 1시간

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

6593번: 상범 빌딩

BOJ 7569 토마토(3차원)와 거의 같은 문제이다.

전역 큐를 사용해 bfs 함수의 매개변수를 없애려다 한 번에 통과가 안됐다.

---

1차 제출 때 메모리 초과 (전역 큐를 이용해 발생한 문제로 추정)

 

1차 제출 이후 알게 된 문제인데, visited 배열도 초기화를 안 했었는데 직접 작성한 여러 테스트 케이스 통과가 이루어졌다. 아마 전역 큐를 사용하며 앞에 이전 TC의 노드 정보가 남아있음에도 visited 배열 초기화가 안돼 bfs에서 E를 만나 종료된 그 직후부터 실행된 후 그 다음 TC가 이루어진 것 같다.

#include <iostream>
#include <string.h>
#include <queue>

using namespace std;
struct P {int x,y,z,n;};
int dx[] = {1,0,-1,0,0,0}, dy[] = {0,1,0,-1,0,0}, dz[] = {0,0,0,0,1,-1};
int C,R,L;
bool visited[31][31][31];
char inp[32][32][32];

bool bound(P a) {return a.x>=0&&a.x<C&&a.y>=0&&a.y<R&&a.z>=0&&a.z<L;}
int bfs(int x,int y,int z) {
    memset(visited,false,sizeof(visited));
    queue<P> Q;
    Q.push({x,y,z,0});
    visited[z][y][x] = true;
    while(!Q.empty()) {
        P tmp = Q.front();
        Q.pop();
        for(int i=0;i<6;++i) {
            P nP = {tmp.x + dx[i],tmp.y + dy[i],tmp.z + dz[i],tmp.n+1};
            if(inp[nP.z][nP.y][nP.x]=='E') return nP.n;
            if(bound(nP)&&!visited[nP.z][nP.y][nP.x]&&inp[nP.z][nP.y][nP.x]=='.') {
                visited[nP.z][nP.y][nP.x] = true;
                Q.push({nP.x,nP.y,nP.z,nP.n});
            }
        }
    }
    return -1;
}

int main() {
    int res;
    int sx,sy,sz;
    while(1) {
        scanf("%d%d%d",&L,&R,&C);
        if(C + R + L == 0) return 0;
        for(int z=0;z<L;++z) {
            for(int y=0;y<R;++y) {
                scanf("%s",&inp[z][y][0]);
                for(int x=0;x<C;++x) {
                    if (inp[z][y][x] == 'S') {
                        sx=x; sy=y; sz=z;
                    }
                }
                getchar();
            }
            getchar();
        }
        // Starting Position S, Exit E

        if((res=bfs(sx,sy,sz))<0)
            cout << "Trapped!" << endl;
        else
            printf("Escaped in %d minute(s).\n",res);
    }
}