[백준]Maaaaaaaaaaze

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

16985번: Maaaaaaaaaze

 

완전탐색과 shift의 범벅... 

--> 순열로 층을 완전탐색해주고 5중 포문을 통해 각 층별로 회전을 시킨 경우 들을 모두 탐색한다.

평면 자체를 시계 혹은 반시계로 회전하는 법에 대해 새로운 방법을 알았다....

(시계방향) 원래 행렬의 1행 ~ 5행을 tmp에 5열~1열에  넣고 tmp를 원래 행렬에 넣어주면된다..

-->행과 열을 바꿔주면 된다.

그리고 이 문제같은 경우, 가장 작게 나올 수 있는 값이 12이므로 12가 나오면 exit로 종료를 해줘서 더욱 빠르게 진행된다.

exit(0)과 같은 경우는 아예 main함수를 종료하기 때문에, 완전탐색중에 답을 딱 찾고 끄고 싶을때 유용할거같다.

 

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
 
struct cube {
    int r, c, h;
};
 
vector<int> v; //순열저장
int d[5] = { 0,1,2,3,4 }; //permitation
bool isV[5]; //순열 방문
int isV1[5][5][5]; //거리저장
int map[5][5][5]; //5개의 5x5판이 있다.
int back[5][5][5]; //backup하고 작업.
int dh[] = { -1,1,0,0,0,0 }, dr[] = { 0,0,1,-1,0,0 }, dc[] = { 0,0,0,0,-1,1 };//위, 아래 , 앞 , 뒤, 왼쪽, 오른쪽
int ans = 1e9;
 
void bfs() {
    memset(isV1, -1, sizeof(isV1));
    queue<cube>q;
    q.push({ 0,0,0 });
    isV1[0][0][0] = 0; //방문
 
    while (!q.empty()) {
        int nr, nc, nh;
        nr = q.front().r, nc = q.front().c, nh = q.front().h;
        q.pop();
 
        if (nr == 4 && nc == 4 && nh == 4) {
            if (isV1[nr][nc][nh] <= ans) ans = isV1[nr][nc][nh];
            if (ans == 12) {
                printf("12\n");
                exit(0); //더 작은값이 나올수 없으므로 12 출력 후 메인종료.
            }
            return;
        }
 
        for (int i = 0; i < 6; i++) {
            int r = nr + dr[i];
            int c = nc + dc[i];
            int h = nh + dh[i];
 
            if (r < 0 || c < 0 || h < 0 || r >= 5 || c >= 5 || h >= 5) continue;
            if (isV1[r][c][h] == -1 && back[r][c][h] == 1) {
                q.push({ r,c,h });
                isV1[r][c][h] = isV1[nr][nc][nh] + 1;
            }
        }
    }
}
 
void Rotation(int h) {
    int temp[5][5];
    //90도 시계방향으로 회전. temp에 행을 열로 저장. (전체를 다 돌리면 이렇게하는게 편함)
    for (int i = 0; i < 5; i++) { 
        for (int j = 0; j < 5; j++) { 
            temp[j][4 - i] = back[h][i][j]; 
        }
    }
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            back[h][i][j] = temp[i][j]; 
        } 
    }
}
 
void solve(int len) {
    if (len == 5) { //순열로 층 구성.
        
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                for (int k = 0; k < 5; k++){
                    back[v[i]][j][k] = map[i][j][k];
                }
            }
        }
 
        for (int a = 0; a < 4; a++) {
            //맨위층
            Rotation(0);
            if (back[0][0][0] == 0) continue; //입구가 없으면.
            for (int b = 0; b < 4; b++) {
                Rotation(1);
                for (int c = 0; c < 4; c ++ ) {
                    Rotation(2);
                    for (int d = 0; d < 4; d++) {
                        Rotation(3);
                        for (int e = 0; e < 4; e++) {
                            Rotation(4);
                            if (back[4][4][4] == 1) bfs(); //출구가 있으면
                        }
                    }
                }
            }
        }
 
        return;
    }
    //순열
    for (int i = 0; i < 5; i++) {
        if (isV[i] == false) {
            isV[i] = true;
            v.push_back(i);
            solve(len + 1);
            isV[i] = false;
            v.pop_back();
        }
    }
 
}
 
void solve() {
    do {
        for (int i = 0; i < 5; i++) { //순열된 순서로 back행렬 초기화
            memcpy(back[d[i]], map[i], sizeof(map[i]));
        }
        for (int i = 0; i < 4; i++) {
            Rotation(0);
            if (!back[0][0][0]) continue;
            for (int j = 0; j < 4; j++) {
                Rotation(1);
                for (int k = 0; k < 4; k++) {
                    Rotation(2);
                    for (int m = 0; m < 4; m++) {
                        Rotation(3);
                        for (int n = 0; n < 4; n++) {
                            Rotation(4);
                            if (back[4][4][4]) bfs();
                        }
                    }
                }
            }
        }
    } while (next_permutation(d, d + 5));
 
}
 
int main()
{
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            for (int k = 0; k < 5; k++) {
                cin >> map[i][j][k]; //1이 들어갈수있는곳.
            }
        }
    }
    
    solve(0); //dfs를 통한 순열구현 
    //solve(); //next_permutation을 이용한 순열
    printf("%d\n", ans == 1e9 ? -1 : ans);
 
    return 0;
}