[백준] 16985번: Maaaaaaaaaze

https://www.acmicpc.net/problem/16985

16985번: Maaaaaaaaaze

문제 이해

문제가 매우 길고 어려워 보이지만 결국 DFS를 통해 모든 경우의 수를 탐색하는 문제이다.

5*5 판을 3번 회전시켜 총 4가지의 경우의 수가 있다. 

이런 판이 5개가 있는데, 이걸 순서를 바꿔가며 쌓을 수 있다.

그리고 이렇게 쌓은 5*5*5의 정육면체에서 한 꼭짓점에서 마주보는 꼭짓점으로 가는 경로의 쌍이 4개가 존재한다 (정육면체 모서리는 8개니까)

즉, 총 5*5*4의 경우의 수를 모두 해봐서, 존재하는 경로의 최단 거리를 구하면 된다.

 

즉,

• DFS의 depth는 5로, 각 depth 별로 판을 하나 선택하고
• 각 판을 4번 회전시키고
• depth == 5가 되었을 때, (정육면체 완선) 4개의 꼭짓점에 BFS를 돌린다

DFS나 BFS는 딱히 어려운 부분 없이 정석적으로 코드를 작성하면 되기 때문에 큰 문제가 없다.

 

작성 코드

#include <iostream>
#include <cstring>
#define INF 0x7fffffff
using namespace std;

int inputMap[5][5][5];
int map[5][5][5];
int visited[5][5][5];

int used[5]; // 판 이용
int tmpmap[5][5];
int ans = 0x7fffffff;

typedef struct p {
    int h, y, x, t;
}POINT;
POINT q[5 * 5 * 5 * 10];
int wp, rp;
void enq(int h, int y, int x, int t) { q[wp].h = h, q[wp].y = y, q[wp].x = x, q[wp++].t = t; }
POINT deq() { return q[rp++]; }
int empty() { return wp == rp; }

int dh[] = { 0, 0, 0, 0, -1, 1 }; // 동서남북상하
int dy[] = { 0, 0, 1, -1, 0, 0 };
int dx[] = { 1, -1, 0, 0, 0, 0 };

void Get_Input(void) {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            for (int k = 0; k < 5; k++) {
                cin >> inputMap[i][j][k];
            }
        }
    }
}

void BFS(int sh, int sy, int sx, int eh, int ey, int ex) {

    if (map[sh][sy][sx] == 0 || map[eh][ey][ex] == 0) return;

    wp = rp = 0;
    memset(visited, 0, sizeof(visited));

    enq(sh, sy, sx, 0);
    visited[sh][sy][sx] = 1;
    while (!empty()) {
        POINT cur = deq();
        if (cur.h == eh && cur.y == ey && cur.x == ex) {
            if (cur.t < ans) ans = cur.t;
            return;
        }
        for (int i = 0; i < 6; i++) {
            int nh = dh[i] + cur.h;
            int ny = dy[i] + cur.y;
            int nx = dx[i] + cur.x;
            if (nh < 0 || nh >= 5 || ny < 0 || ny >= 5 || nx < 0 || nx >= 5) continue;
            if (visited[nh][ny][nx] == 1) continue;
            if (map[nh][ny][nx] == 0) continue;
            enq(nh, ny, nx, cur.t + 1);
            visited[nh][ny][nx] = 1;
        }
    }
}

void Print_Map(int idx) {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            cout << inputMap[idx][i][j];
        }
        cout << "\n";
    }
    cout << "\n";
}


void DFS(int cnt) {
    // cnt: 지금까지 쌓은 거
    // 종료
    int ret;
    if (cnt == 5) {
        // 꼭짓점 선택해서 BFS -> 총 4쌍
        BFS(0, 0, 0, 4, 4, 4);
        BFS(0, 4, 0, 4, 0, 4);
        BFS(0, 0, 4, 4, 4, 0);
        BFS(0, 4, 4, 4, 0, 0);
        return;
    }

    // 재귀
    // 0. 선택하기
    for (int i = 0; i < 5; i++) {
        if (used[i] == 1) continue;
        used[i] = 1;
        for (int l = 0; l < 4; l++) {
            // 1. 맵에 올리기
            for (int j = 0; j < 5; j++) {
                for (int k = 0; k < 5; k++) {
                    map[cnt][j][k] = inputMap[i][j][k];
                }
            }
            // 2. 다음 맵 선택을 위한 DFS
            DFS(cnt + 1);
            // 3. 돌리기
            memset(tmpmap, 0, sizeof(tmpmap));
            for (int j = 0; j < 5; j++) {
                for (int k = 0; k < 5; k++) {
                    tmpmap[k][4 - j] = inputMap[i][j][k];
                }
            }
            memcpy(inputMap[i], tmpmap, sizeof(tmpmap));
        }
        used[i] = 0;
    }
}

int main(void) {
    freopen("in.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Get_Input();
    DFS(0);
    if (ans == INF) cout << "-1";
    else cout << ans;
    return 0;
}