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

문제

문제에서 추출할 수 있는 정보는 다음과 같다.

• 정육면체 -> 3차원 좌표를 활용해야 한다.
• 지나갈 수 없는 칸은 '#'이다.
• S에서 E까지 이동하는 최단 거리를 찾으면 된다.

입출력

보편적인 BFS 최단시간 문제를 3차원으로 확장한 것임을 알 수 있다.

시행착오

• 테스트 케이스마다 Queue를 초기화하지 않아서 시간이 더 걸렸다.
• string을 입력받아 char 3차원 배열로 조정하는 과정에서 인덱스를 잘못 사용했다.

소스 코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;
int l, r, c;
int visited[31][31][31]; // 소요 시간을 저장하는 역할을 추가로 부여
char map[31][31][31];
int dx[6] = {1, 0, 0, -1, 0, 0}; // 정육면체 내에서 이동
int dy[6] = {0, 1, 0, 0, -1, 0};
int dz[6] = {0, 0, 1, 0, 0, -1};

struct pos{ // 좌표를 담은 구조체
    int x, y, z;
    pos(int ax, int ay, int az){
        x = ax;
        y = ay;
        z = az;
    }
};

int sx, sy, sz, fx, fy, fz; // 시작점과 도착점

void BFS(int sx, int sy, int sz){
    queue<pos> q;
    visited[sx][sy][sz] = 1;
    q.push(pos(sx, sy, sz));

    while(!q.empty()){ // BFS
        pos p = q.front();
        q.pop();

        if(p.x == fx && p.y == fy && p.z == fz){ // 도착
            cout << "Escaped in " << visited[fx][fy][fz] - 1 << " minute(s)." << '\n';
            return;
        }

        for(int i=0; i<6; i++){
            int nx = p.x + dx[i];
            int ny = p.y + dy[i];
            int nz = p.z + dz[i];

            if(nx < 0 || ny < 0 || nz < 0 || nx >= l || ny >= r || nz >= c) continue; // 범위 이탈
            if(map[nx][ny][nz] == '#') continue; // #는 갈 수 없음
            if(!visited[nx][ny][nz]){
                visited[nx][ny][nz] = visited[p.x][p.y][p.z] + 1;
                q.push(pos(nx, ny, nz));
            }
        }
    }
    cout << "Trapped!" << '\n'; // 도착 불가능한 경우
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    while(1){
        memset(visited, 0, sizeof(visited)); // 테케별 초기화 필요
        cin >> l >> r >> c;
        if(l == 0 && r == 0 && c == 0){ // 종료
            break;
        }

        for(int i=0; i<l; i++){
            for(int j=0; j<r; j++){
                string str;
                cin >> str;
                for(int k=0; k<c; k++){
                    map[i][j][k] = str[k];
                    if(str[k] == 'S'){ // 시작점 저장
                        sx = i;
                        sy = j;
                        sz = k;
                    }
                    if(str[k] == 'E'){ // 도착점 저장
                        fx = i;
                        fy = j;
                        fz = k;
                    }
                }
            }
        }
        BFS(sx, sy, sz);
    }
    return 0;
}

교훈

• BFS는 전체적인 구도를 빠르고 정확하게 잡는 것이 중요하다.
• 항상 인덱스 사용이나 테스트케이스별 자료형 초기화가 적절하게 이루어지는지 검증하자.