백준 16985 Maaaaaaaaaze

BFS와 시뮬레이션이 합쳐진 응용문제라 할 수 있다.

• 조건
  • 5x5 크기의 판이 5개가 주어진다.
  • 판의 순서는 바꿀 수 있고, 각 판은 시계방향 또는 반시계방향으로 회전이 가능하다.
  • 구해야 할 것은 (0, 0, 0)에서 (4, 4, 4)까지의 최단거리이다.
• 목표
  • 각 판을 어떻게 회전하고, 판의 순서가 어떻게 될 지 주어진 것이 없기 때문에 모든 경우의 수의 최단거리를 구하고 최솟값을 출력하면 된다.
  • 입력받은 값에서 조사할 maze 값을 뽑은 뒤에, BFS를 돌리고 최단거리를 구한다.
• 순서
  • 회전을 모두 하고난 뒤에 판의 순서를 정해야 한다.
  • 회전을 하는 경우의 수는 모두 4가지이다. 그렇기 때문에 처음 데이터를 받을 때 3차원 배열에서 차원을 하나 더 늘려 각 판이 회전하는 4가지 경우의 수를 모두 추가해준다.
  • 각 판의 순서를 정해야 하는데, 5개의 판 중 5개를 뽑는 순열이므로 next_permutation을 이용한다.
  • 회전하는 경우의 수를 모두 따져보면 총 4^5의 경우의 수가 나온다. 4진법을 이용해서 각 회전하는 경우의 수를 받고, next_permutation을 이용하여 각 판의 경우의 수를 받아 BFS를 돌릴 maze 값을 받는다.
  • 받은 maze 값을 이용하여 BFS를 돌리고 최단 거리를 구한다.

정답 코드

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

int board[4][5][5][5];
int maze[5][5][5];
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 solve() {
    int dist[5][5][5] = {0, };
    if(!maze[0][0][0] || !maze[4][4][4]) return 9999;
    queue<tuple<int, int, int>> q;
    q.push({0, 0, 0});
    dist[0][0][0] = 1;
    while(!q.empty()) {
        tuple<int, int, int> cur = q.front(); q.pop();
        for(int dir = 0; dir < 6; dir++) {
            int x, y, z; tie(x, y, z) = cur;
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            int nz = z + dz[dir];
            if(nx < 0 || nx >= 5 || ny < 0 || ny >= 5 || nz < 0 || nz >= 5) continue;
            if(!maze[nx][ny][nz] || dist[nx][ny][nz] != 0) continue;
            if(nx == 4 && ny == 4 && nz == 4) {
                return dist[x][y][z];
            }
            q.push({nx, ny, nz});
            dist[nx][ny][nz] = dist[x][y][z]+1;
        }
    }
    return 9999;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    for(int i = 0; i < 5; i++) {
        for(int j = 0; j < 5; j++) {
            for(int k = 0; k < 5; k++) {
                cin >> board[0][i][j][k];
            }
        }
        for(int j = 0; j < 5; j++) {
            for(int k = 0; k < 5; k++) {
                board[1][i][j][k] = board[0][i][4-k][j];
            }
        }
        for(int j = 0; j < 5; j++) {
            for(int k = 0; k < 5; k++) {
                board[2][i][j][k] = board[1][i][4-k][j];
            }
        }
        for(int j = 0; j < 5; j++) {
            for(int k = 0; k < 5; k++) {
                board[3][i][j][k] = board[2][i][4-k][j];
            }
        }
    }
    int order[5] = {0, 1, 2, 3, 4};
    int ans = 9999;
    do {
        for(int tmp = 0; tmp < 1024; tmp++) {
            int brute = tmp;
            for(int i = 0; i < 5; i++) {
                int dir = brute%4;
                brute /= 4;
                for(int j = 0; j < 5; j++) {
                    for(int k = 0; k < 5; k++) {
                        maze[i][j][k] = board[dir][order[i]][j][k];
                    }
                }
            }
        ans = min(ans, solve());
        }
    } while(next_permutation(order, order+5));
    if(ans == 9999) ans = -1;
    cout << ans << '\n';
}