[BOJ / C++] 상범 빌딩 (BFS)

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

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

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

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

    while (true) {
        int l, r, c;
        cin >> l >> r >> c;
        if (l==0 && r==0 && c==0) break;

        queue<tuple<int, int, int>> Q;

        vector<vector<vector<char>>> board(l, vector<vector<char>>(r, vector<char>(c, ' ')));
        vector<vector<vector<int>>> dist(l, vector<vector<int>>(r, vector<int>(c, -1)));
        
        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++) {
                    board[i][j][k] = str[k];
                    if (board[i][j][k] == 'S') {
                        Q.push({i, j, k});
                        dist[i][j][k] = 0;
                    }
                }
            }
        }
        
        int answer = 0;
        bool escape = false;

        while (!Q.empty() && !escape) {
            auto cur = Q.front(); Q.pop();
            int x, y, z;
            tie(x, y, z) = cur;
            
            for (int dir = 0; dir < 6; dir++) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                int nz = z + dz[dir];
                
                if (nx < 0 || ny < 0 || nz < 0 || nx >= l || ny >= r || nz >= c) continue;
                if (board[nx][ny][nz] == '#' || dist[nx][ny][nz] >= 0) continue;
                
                if (board[nx][ny][nz] == 'E') {
                    answer = dist[x][y][z] + 1;
                    escape = true;
                    break;
                }

                Q.push({nx, ny, nz});
                dist[nx][ny][nz] = dist[x][y][z] + 1;
            }
        }

        if (escape) {
            cout << "Escaped in " << answer << " minute(s).\n";    
        }
        else {
            cout << "Trapped!\n";
        } 
    }
}

 

 

2. 분석

3차원 미로탈출 BFS 문제이다. 입력받을 때 층과 층은 \n 줄바꿈으로 구분해서 이걸 별도로 처리해야하나 생각했는데, cpp에서 cin >> str 은 공백(개행, 스페이스 등)을 모두 무시하고 다음 토큰(여기서는 “문자열”)만 읽어오기 때문에 별도로 처리하지 않아도 된다. 미로 문제에서 dist 배열을 -1로 초기화하면 vis 배열을 생략할 수 있다. 대신 입력을 받을 때 바로 'S'를 발견하면 큐에 push 했는데 이때 dist[i][j][k] = 0으로 반드시 초기화해줘야한다. 이 부분을 빼먹어서 처음에 오류가 발생했었다.

if (nx < 0 || ny < 0 || nz < 0 || nx >= l || ny >= r || nz >= c) continue;
if (board[nx][ny][nz] == '#' || dist[nx][ny][nz] >= 0) continue;

if (board[nx][ny][nz] == 'E') {
    answer = dist[x][y][z] + 1;
    escape = true;
    break;
}

 

범위 바깥으로 나갔는지 여부 체크를 항상 제일 먼저 해줘야한다. 이 순서를 헷갈리면 Out of Bound 의문사를 당할 수 있다. 

 

3. 시간복잡도

시간복잡도는 O(l * r * c)이다. 시간제한은 1초이고, 30 * 30 * 30 = 27000 < 10^8 이므로 충분하다.