백준 6593번 상범 빌딩 C++ BFS

리뷰

각 테스트 케이스마다 맵을 초기화 해주어야 하는데 해당 부분을 까먹어 OutOfBounds 에러가 노출되었다.

 

문제 풀이

1. 2차원 string 배열을 초기화 해준다. l * r 크기로 초기화 해준 뒤 문자열을 입력 받는다.
2. 문자열의 각 요소를 훑고 만약 S를 찾았다면 시작 위치 좌표로, E를 찾았다면 종료 위치 좌표로 저장해 준다. 이후 빈 칸 '.'로 초기화를 해준다.
3. bfs를 실행해 준 뒤 1개의 방향, 상하좌우 및 위층과 아래층의 방향으로 탐색을 해준다.
4. while 루프가 종료되기 전 목적지에 도착한 경우 해당 시간을 리턴, while루프가 종료된 경우 -1 을 리턴해 준다.
5. bfs 결과가 -1을 리턴한 경우 Trapped!을 출력, 아닌 경우 Escaped in (리턴 값) minute(s).을 출력해 준다.

 

참고 사항

l, r, c가 모두 0으로 입력받은 경우 테스트 케이스를 종료한다.

출발지와 도착지의 좌표를 받은 후 '.'로 변환을 해주던지 bfs 내 기저 조건에 E를 찾은 경우로 설정해 준다.

 

정답 코드

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int l, r, c;
int sx, sy, sz, dx, dy, dz;
int dirx[] = { 1, 0, 0, 0, 0, -1 };
int diry[] = { 0, 1, -1, 0, 0, 0 };
int dirz[] = { 0, 0, 0, 1, -1, 0 };


struct Pos {
    int x, y, z, time;
};

int bfs(vector<vector<string>>& lst) {
    queue<Pos> q;
    q.push({ sx, sy, sz, 0 });
    int v[31][31][31] = { 0 };

    while (!q.empty()) {
        Pos pos = q.front(); q.pop();
        int x = pos.x, y = pos.y, z = pos.z, t = pos.time;
        if (x == dx && y == dy && z == dz) return t;

        for (int i = 0; i < 6; i++) {
            int nx = x + dirx[i], ny = y + diry[i], nz = z + dirz[i], nt = t + 1;
            if (0 <= nx && nx < l && 0 <= ny && ny < r && 0 <= nz && nz < c && !v[nx][ny][nz] && lst[nx][ny][nz] == '.') {
                v[nx][ny][nz] = 1;
                q.push({ nx, ny, nz, nt });
            }
        }
    }
    return -1;
}

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

    while (1) {
        cin >> l >> r >> c;
        if (!l && !r && !c) break;
        vector<vector<string>> lst(l, vector<string>(r));
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < r; j++) {
                cin >> lst[i][j];
                for (int k = 0; k < c; k++) {
                    if (lst[i][j][k] == 'S') {
                        sx = i, sy = j, sz = k;
                        lst[i][j][k] = '.';
                    }
                    if (lst[i][j][k] == 'E') {
                        dx = i, dy = j, dz = k;
                        lst[i][j][k] = '.';
                    }
                }
            }
        }
        int ans = bfs(lst);
        if (ans != -1) cout << "Escaped in " << ans << " minute(s).\n";
        else cout << "Trapped!\n";
    }
}