[백준(BOJ)] 6593번 상범 빌딩 C++

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

6593번: 상범 빌딩

 

 

어떤 문제인가?

이 문제는 기존의 2차원에서 움직이던 그래프 탐색이 아니라 3차원으로 이동해야 한다.

시작 좌표 S부터 움직여가며 도착 좌표 E까지 이동하는 게 걸리는 시간을 출력하면 된다.

 

접근 방법

 

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};

위의 배열들은 x, y, z 축으로 움직이기 위한 것이다.

 

char building[31][31][31];
bool visited[31][31][31];
int dist[31][31][31];

건물의 각 위치의 종류를 저장할 삼차원 배열, 방문 여부를 저장할 삼차원 배열, 이동거리를 저장할 삼차원 배열을 선언해준다.

 

void bfs(int z, int y, int x) {
    queue<Q> q;
    q.push({z, y, x});
    visited[z][y][x] = true;

    while (!q.empty()) {
        int y1 = q.front().y;
        int x1 = q.front().x;
        int z1 = q.front().z;
        q.pop();

        for (int i = 0; i < 6; i++) {
            int y2 = y1 + dy[i];
            int x2 = x1 + dx[i];
            int z2 = z1 + dz[i];

            if (x2 < 0 || y2 < 0 || z2 < 0 || x2 >= c || y2 >= r || z2 >= l) {
                continue;
            }

            if (building[z2][y2][x2] == '#') {
                continue;
            }

            if (building[z2][y2][x2] == 'E') {
                dist[z2][y2][x2] = dist[z1][y1][x1] + 1;
                cout << "Escaped in " << dist[z2][y2][x2] << " minute(s).\n";
                return;
            }

            if (building[z2][y2][x2] == '.' && !visited[z2][y2][x2]) {
                q.push({z2, y2, x2});
                visited[z2][y2][x2] = true;
                dist[z2][y2][x2] = dist[z1][y1][x1] + 1;
            }
        }
    }
    cout << "Trapped!\n";
}

bfs함수를 살펴보자.

이 문제는 x, y, z좌표를 저장해야했다. 그래서

struct Q {
    int z;
    int y;
    int x;
};

Q라는 구조체를 정의해서 그 안에 좌표를 저장하는 방법을 사용했다.

 

이제 다른 bfs와 같이 탐색을 시작해보자.

x, y, z좌표를 위의 말했던 dx, dy, dz배열을 통해 이동시킨다.

 

이동한 좌표가 l*r*c의 범위를 벗어나거나 막혔다면(#) 넘어가 준다.

 

그리고 만약 이동한 좌표의 값이 E라면 도착한 것이다.

따라서 거리를 1 증가시켜주고 문제의 요구대로 이동한 거리를 출력해주면 된다.

 

만약 이동한 좌표의 값이.(점)이고 방문하지 않았다면,

방문처리를 해주고 거리를 1 증가시켜준다.

 

dist [ z ] [ y ] [ x ] = 3의 뜻은

(x, y, z)까지 거리가 3이라는 뜻이다.

 

만약 while문이 끝났을 때도 함수가 종료되지 않았다는 것은 좌표가 이동하면서 E를 만나지 못했다는 것이다.

그러므로 Trapped! 를 출력해준다.

 

while (true) {
    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++) {
            for (int k = 0; k < c; k++) {
                cin >> building[i][j][k];
            }
        }
    }

    for (int i = 0; i < l; i++) {
        for (int j = 0; j < r; j++) {
            for (int k = 0; k < c; k++) {
                if (building[i][j][k] == 'S') {
                    bfs(i, j, k);
                }
            }
        }
    }

    reset();
}

이제 main함수를 살펴보자.

l, r, c가 모두 0이 입력될 때까지 반복한다.

 

먼저 building 배열을 입력받는다.

그리고 입력받은 배열을 돌며 값이 S라면 그 좌표로 bfs를 시작한다.

 

void reset() {
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < r; j++) {
            for (int k = 0; k < c; k++) {
                building[i][j][k] = 0;
                visited[i][j][k] = 0;
                dist[i][j][k] = 0;
            }
        }
    }
}

bfs를 한 번 수행하고 나면 reset함수로 사용했던 배열들을 초기화시켜준다.

 

l, r, c가 모두 0이 입력될 때까지 반복하면 끝!

 

 

무엇이 어려웠는가?

기존에 풀던 그래프 탐색은 2차원이었다.

3차원 그래프 탐색은 처음이었다.

하지만 별 다를거 없이 dz배열에 맞춰 dx, dy만 조금 바꿔주니 큰 어려움이 없었다.

 

그리고 큐에 저장해야할 값이 세 가지라 어떻게 해야 할지 고민했다.

여태껏 문제를 풀며 구조체를 사용할 일이 없어서 구조체를 까먹고 있었는데

이 문제를 풀면서 구조체를 오랜만에 사용해봤다.

 

그 외에는 큰 고민 없이 문제를 풀 수 있었다.

 

 

느낀 점

알고리즘... 재밌다...

언젠가 백준 플레 찍는 상상하며 열심히 하자!