[DFS+BFS] BJ16985 Maaaaaaaaaze

문제 출처: https://www.acmicpc.net/problem/16985

 

Solution

• 3차원 퍼즐의 각 층을 쌓는 부분과 각 층을 회전시키는 부분은 DFS로 경우의 수를 완전 탐색하고, 퍼즐이 완성되면 목적지까지 거리를 BFS로 탐색한다.

Point

• 퍼즐을 만들기 위해 가능한 모든 경우의 수를 완전 탐색해야하는데, 이 부분이 좀 까다롭다.
• DFS를 이중으로 사용해서 해결했는데, 차라리 단순히 for문으로 하거나 next_permutation를 이용하는게 더 쉬울 것 같다.
• 처음에 시작 지점이 여러군데 존재할 수 있다고 생각했는데, 어차피 퍼즐을 돌리면서 시도해보기 때문에 (0,0,0)에서만 해보면 된다.
• 롤백을 위해 메모리 복사를 많이 해서 그런지 속도가 꽤 느리다.

---

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

int result;
int map[5][5][5];
int new_map[5][5][5];
int dist[5][5][5];
int visit[5];
int dx[] = { -1, 1, 0, 0, 0, 0 };
int dy[] = { 0, 0, -1, 1, 0, 0 };
int dz[] = { 0, 0, 0, 0, -1, 1 };
int in[1][3] = { {0, 0, 0}};
int out[1][3] = { {4, 4, 4}};

struct xyz {
    int z, y, x;
};

void input() {
    result = 987654321;
    for (int z = 0; z < 5; z++)
        for (int y = 0; y < 5; y++)
            for (int x = 0; x < 5; x++)    
                cin >> map[z][y][x];
}

int calDistBFS(int start[], int end[]) {
    memset(dist, 0, sizeof(dist));
    queue<xyz> q;
    dist[start[0]][start[1]][start[2]] = 1;
    q.push({ start[0], start[1], start[2] });
    while (!q.empty()) {
        xyz cur = q.front();
        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 || ny < 0 || nz < 0 || nx >= 5 || ny >= 5 || nz >= 5) continue;
            if (nz == end[0] && ny == end[1] && nx == end[2]) {
                    return dist[cur.z][cur.y][cur.x];
            }
            if (new_map[nz][ny][nx] && !dist[nz][ny][nx]) {
                q.push({ nz, ny, nx });
                dist[nz][ny][nx] = dist[cur.z][cur.y][cur.x] + 1;
            }
        }
    }
    return 987654321;
}

void rotate(int z, int nr) {
    if (nr == 0) return;
    int ny[] = { 4, 3, 2, 1, 0 };
    for (int n = 0; n < nr; n++) {
        int tmp[5][5];
        for (int y = 0; y < 5; y++)
            for (int x = 0; x < 5; x++)
                tmp[x][ny[y]] = new_map[z][y][x];
        memcpy(new_map[z], tmp, sizeof(new_map[z]));
    }
}

void rotateDFS(int cur, int d) {
    if (d == 5) {
        if (new_map[in[0][0]][in[0][0]][in[0][2]] && new_map[out[0][0]][out[0][1]][out[0][2]])
            result = min(calDistBFS(in[0], out[0]), result);
        return;
    }
    for (int i = 0; i < 4; i++) {
            int tmp[5][5];
            memcpy(tmp, new_map[d], sizeof(new_map[d]));
            rotate(d, i);
            rotateDFS(i, d + 1);
            memcpy(new_map[d], tmp, sizeof(new_map[d]));
    }
}

void stackupDFS(int cur, int d) {
    if (d == 5) {
        rotateDFS(0, 0);
        return;
    }
    for (int i = 0; i < 5; i++) {
        if (!visit[i]) {
            memcpy(new_map[d], map[i], sizeof(map[i]));
            visit[i] = true;
            stackupDFS(i, d + 1);
            visit[i] = false;
        }
    }
}

int main() {
    input();
    stackupDFS(0, 0);
    if (result == 987654321) cout << -1 << endl;
    else cout << result << endl;
}