[백준] 16985 Maaaaaaaaaze

16985번: Maaaaaaaaaze

 

www.acmicpc.net

풀이

구현이 까다로운 문제이다. 이 문제는 완전탐색으로 해결하였다. 이 문제는 크게 세가지의 구현을 해내면 풀 수 있다.
1. 5x5 크기의 판 쌓기 (Permutation)
2. 5x5 크기의 판 돌리기
3. 3차원 최단 경로 찾기 (BFS)

우선 5x5 크기의 판 쌓기는 순열을 사용해서 간단히 구현할 수 있다. 각 판의높이를 나타내는 숫자 배열 h = \[0, 1, 2, 3, 4\]가 있다고 하자. h 배열의 숫자를 정렬하는 방법은 [0, 1, 2, 3, 4]부터 [4, 3, 2, 1, 0]까지 총 120가지의 경우가 나온다. 따라서 이를 이용하면 판을 쌓는 모든 경우를 쉽게 구현할 수 있다.

이번엔 5x5 크기의 판 돌리기를 알아보자. 2차원 배열을 돌리는 경우는 쉽게 구현할 수 있다. 자주 이용되니 코드를 보고 숙지할 수 있도록 하자.

void rotate_board(int idx) {
    int tmp[5][5];
    memcpy(tmp, board[idx], sizeof(tmp));
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            board[idx][i][j] = tmp[n - 1 - j][i];
}

이번엔 3차원 최단 경로 찾기 (BFS)이다. 3차원의 최단 경로를 찾는 것은 2차원 배열에서 BFS를 사용해서 최단경로를 찾는 것과 크게 다르지 않다. 중복 제거를 위한 visited배열을 3차원으로 만들어주고, 좌표를 3차원으로 조작해주며 탐색해주면 된다.

마지막으로 이 문제는 약간의 최적화를 통해 시간을 대폭 감소시킬 수 있다. 3차원의 미로에서 모든 면이 이동 가능할 때 최단 경로는 12가 된다. 즉 이 말은 3차원에서 아무리 빨리 이동해도 12보다는 작은 값이 나올 수 없다는 의미이다. 따라서 완전탐색을 하는 도중 12라는 값을 찾았다면 그 즉시 프로그램을 종료시켜도 된다는 의미이다.

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <climits>
#include <cstring>
using namespace std;

struct Point {
    int x, y, z, cnt;
};

int n, ans = INT_MAX;
int board[5][5][5];
int buff[5][5][5];
bool visited[5][5][5];
const int dx[] = { 0, 1, 0, -1, 0, 0 }, dy[] = { -1, 0, 1, 0, 0, 0 }, dz[] = { 0, 0, 0, 0, 1, -1 };

void rotate_board(int idx) {
    int tmp[5][5];
    memcpy(tmp, board[idx], sizeof(tmp));
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            board[idx][i][j] = tmp[n - 1 - j][i];
}

int bfs() {
    memset(visited, false, sizeof(visited));
    queue<Point> q;
    q.push({ 0, 0, 0, 0 });
    visited[0][0][0] = true;


    while (!q.empty()) {
        Point cur = q.front();
        int cnt = cur.cnt;
        if (cur.x == 4 && cur.y == 4 && cur.z == 4) return cnt;
        if (cnt >= ans) return INT_MAX;
        q.pop();

        for (int i = 0; i < 6; i++) {
            int nx = cur.x + dx[i]; int ny = cur.y + dy[i]; int nz = cur.z + dz[i];
            if (nx < 0 || nx > 4 || ny < 0 || ny > 4 || nz < 0 || nz > 4) continue;
            if (!visited[nz][ny][nx] && board[nz][ny][nx]) {
                q.push({ nx, ny, nz, cnt + 1 });
                visited[nz][ny][nx] = true;
            }
        }
    }
    return INT_MAX;
}

void shuffle() {
    int h[] = { 0, 1, 2, 3, 4 };
    // 쌓는 순서를 조합을 사용해서 결정
    do {
        // board에 면들을 쌓아서 저장
        for (int i = 0; i < 5; i++) memcpy(board[h[i]], buff[i], sizeof(buff[i]));

        // 맨 윗층부터 돌린다
        for (int i = 0; i < 4; i++) {
            rotate_board(0);
            // 출발점으로 들어갈 수 없는 경우를 건너뛰어 최적화해준다
            if (!board[0][0][0]) continue;
            for (int j = 0; j < 4; j++) {
                rotate_board(1);
                for (int k = 0; k < 4; k++) {
                    rotate_board(2);
                    for (int l = 0; l < 4; l++) {
                        rotate_board(3);
                        for (int m = 0; m < 4; m++){
                            rotate_board(4);
                            ans = min(ans, bfs());
                            // 12를 찾았으므로 종료
                            if (ans == 12) {
                                cout << ans << '\n';
                                exit(0);
                            }
                        }
                    }
                }
            }
        }        
    } while (next_permutation(h, h + 5));
    cout << (ans == INT_MAX ? -1 : ans) << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    n = 5;
    for (int l = 0; l < 5; l++)
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
                cin >> buff[l][i][j];
    shuffle();
    return 0;
}