BOJ 16985 Maaaaaaaaaze

사용한 알고리즘

BFS, 완전탐색

알고리즘 설명

큐브의 크기가 5로 완전탐색이 가능하다.
각 큐브 5x5가 5개 있다.
5x5 각각 5개의 놓이는 순서를 정한다.
순서를 정한뒤, 모든 위치에서 시계방향으로 돌리는 4가지 경우를 본다.
(1,1)에서 (5,5)까지 최소 거리를 BFS로 찾는다.
(5!)x(4^5)x(5x5) = 약 300만으로 충분하다.
최소 거리를 출력한다.

풀이

// baekjoon 16985 yechan
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int INF=1e9;
const int dir[6][3]={
    {0, 0, 1},
    {0, 0, -1},
    {0, 1, 0},
    {0, -1, 0},
    {1, 0, 0},
    {-1, 0, 0}
};

struct Point{
    int x, y, z;
    Point(){}
    Point(int x, int y, int z):x(x), y(y), z(z){}
};

int board[4][5][5][5];
bool check[5];

int block[5];
int rot[5];

bool visited[5][5][5];

int ret=INF;

void bfs() {
    queue<Point> q;
    if (!board[rot[0]][block[0]][0][0]) return;
    if (!board[rot[4]][block[4]][4][4]) return;
    memset(visited, 0, sizeof(visited));

    q.push(Point(0,0,0));
    visited[0][0][0]=true;

    int depth=0;
    while (!q.empty()) {
        int qSize = q.size();
        while (qSize--) {
            int x = q.front().x;
            int y = q.front().y;
            int z = q.front().z;
            q.pop();
            if (x == 4 && y == 4 && z == 4) {
                ret = min(ret, depth);
                return;
            }
            for (int i=0; i<6; i++) {
                int nx = x + dir[i][0];
                int ny = y + dir[i][1];
                int nz = z + dir[i][2];
                if (nx < 0 || nx >= 5) continue;
                if (ny < 0 || ny >= 5) continue;
                if (nz < 0 || nz >= 5) continue;
                if (visited[nx][ny][nz]) continue;
                if (!board[rot[nx]][block[nx]][ny][nz]) continue;
                visited[nx][ny][nz]=true;
                q.push(Point(nx, ny, nz));
            }
        }
        depth++;
    }
}

void dfs(int num) {
    if (num == 5) {
        bfs();
        return;
    }
    for (int i=0; i<5; i++) {
        if (check[i]) continue;
        check[i]=true;
        block[num]=i;
        for (int r=0; r<4; r++) {
            rot[num]=r;
            dfs(num+1);
        }
        block[num]=0;
        check[i]=false;
    }
}

int main() {
    for (int i=0; i<5; i++)
        for (int j=0; j<5; j++)
            for (int k=0; k<5; k++)
                scanf("%d", &board[0][i][j][k]);

    for (int r=0; r<3; r++)
        for (int i=0; i<5; i++)
            for (int j=0; j<5; j++)
                for (int k=0; k<5; k++)
                    board[r+1][i][4-k][j]=board[r][i][j][k];

    dfs(0);
    printf("%d\n", (ret==INF) ? -1 : ret);

    return 0;
}