백준 16985 Maaaaaaaaaze

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

16985번: Maaaaaaaaaze

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
int input[5][5][5];
int map[5][5][5];
int r[] = { 3,3,3,3,3 };
void copy(int cinput[5][5], int input[5][5]) {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            cinput[i][j] = input[i][j];
        }
    }
}
void rot(int idx) {
    int cinput[5][5];
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            cinput[j][i] = input[idx][5 - i - 1][j];
        }
    }
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            input[idx][i][j] = cinput[i][j];
        }
    }
}
int dy[6] = { 0, 0, 0, 1, 0, -1 };
int dx[6] = { 0, 0, 1, 0, -1, 0 };
int dz[6] = { 1, -1, 0, 0, 0, 0 };
int ret = 0x7fffffff;
int chk[5][5][5] = { 0, };
struct Data {
    int y, x, z, cnt;
};
void bfs() {
    queue<Data>q;
    q.push({ 0,0,0,0 });
    int chk[5][5][5] = { 0, };
    chk[0][0][0] = 1;
    if (map[0][0][0] == 1 && map[4][4][4] == 1) {
        while (!q.empty()) {
            Data c = q.front(); q.pop();
            if (c.y == 4 && c.x == 4 && c.z == 4) {
                if (ret > chk[4][4][4]) ret = chk[4][4][4];
                return;
            }
            for (int dir = 0; dir < 6; dir++) {
                Data n = c;
                n.y += dy[dir];
                n.x += dx[dir];
                n.z += dz[dir];
                n.cnt++;
                if (0 <= n.z && n.z < 5 && 0 <= n.y && n.y < 5 && 0 <= n.x && n.x < 5) {
                    if (chk[n.z][n.y][n.x] == 0 && map[n.z][n.y][n.x] == 1) {
                        chk[n.z][n.y][n.x] = n.cnt;
                        q.push(n);
                    }
                }
            }
        }
    }
    else return;
}
void dfs(int idx, int d) {
    if (idx > 15)return;
    else {
        int num[5] = { 0,1,2,3,4 };
        for (int k = 0; k < 5; k++) {
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    map[k][i][j] = input[num[k]][i][j];
                }
            }
        }
        memset(chk, 0, sizeof(chk));
        chk[0][0][0] = 1;
        bfs();
        while (next_permutation(num, num + 5)) {
            for (int k = 0; k < 5; k++) {
                for (int i = 0; i < 5; i++) {
                    for (int j = 0; j < 5; j++) {
                        map[k][i][j] = input[num[k]][i][j];
                    }
                }
            }
            memset(chk, 0, sizeof(chk));
            chk[0][0][0] = 1;
            bfs();
        }
    }
    for (int i = d; i < 5; i++) {
        if (r[i] == 0)continue;
        int cinput[5][5] = { 0, };
        copy(cinput, input[i]);
        rot(i);
        r[i]--;
        dfs(idx + 1, i);
        r[i]++;
        copy(input[i], cinput);
    }
}
void init() {
    for (int k = 0; k < 5; k++) {
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                scanf("%d", &input[k][i][j]);
            }
        }
    }
}
int main(void)
{
    init();
    dfs(0, 0);
    if (ret == 0x7fffffff) ret = -1;
    printf("%d", ret);
    return 0;
}
 

이문제는 처음 보면 당황스러울수 있습니다 3차원으로 미로 탐색을 해야하기때문에 그럴 수 있지만 
사실 2차원 으로 x , y 방향으로 탐색을 하던 방식을
3차원으로 생각만 하면 됩니다 
우선 x y 일때 우리는 
dy[] = {0, -1, 0, 1 };
dx[] = {-1, 0, 1, 0}; 인것을 
dz축에 대해서 확장 시키면 됩니다 
그렇게 하면 
​

z축 까지 표현을 하게 된다면 이렇게 해서 기본 dfs를 돌리면 알아서 찾아가게 됩니다.

삼차원으로 탐색하는것은 알겠는데 나는 배열을 돌리고 또 그 배열에 대해서 순열 같이 뽑는것을 모르겠다 하시면 
블로그에 순열 조합에 모든것을 보시고 익히시면됩니다 
이문제는 그렇게 돌리는것에 대해서도 순열을 뽑아야하고 돌려진 블록에대해서도 순열을 돌려야해서 복잡할수 있어요 
저는 그래서 돌려진 블록에 대해서는 다음순열 stl을 이용해서 했습니다. 
다음순열의 경우 algorithm 의 헤더파일에
들어있으니 참고하시고 소스 보시고 저런 방식으러 쓸수 있구나 생각 하시면 됩니다

저도 처음에 순열은 다 구해놓고 3차원 방식의 너비탐색을 처음 해봐서 되나 고민하다 조금 시간이 걸렸거든요 
아직 더 많이 공부를 해야하나봅니다
무튼 위의 소스 보시고 참고 하시면 됩니다 
오늘은 여기까지 이고 즐거운 코딩 하세요


​