[BOJ.16985번] Maaaaaaaaaze

반응형

문제 링크 :  https://www.acmicpc.net/problem/16985

 

이 문제는 완전탐색과 bfs와 극한의 시뮬레이션이 포함된 문제이다..!!

처음에 문제를 봤을 때 극한의 문제다!! 하고 겁을 먹었지만 막상 구현을 해보니 그리 어렵지 않은 문제였다.

 

먼저, 5개 층의 순서를 섞어줄 때 #include<algorithm>에 있는 nextpermutation함수를 사용해 조합을 만들어주었다.

5개 층의 순서가 결정되면, 이제 시계방향으로 각층마다 돌려준다.

이때, 반시계방향은 고려할 필요가 없는게 어차피 시계방향으로 3번 돌리면 제자리로 오고 모든 경우를 본 것이기 때문이다.

시계방향으로 돌려주는 함수는 rotation함수로 main에서 5중포문으로 조합을 구현하였다....(선생님,,,설마 코드에 6중포문을 넣으신 겁니까...???)

이부분은 더 좋은 방법이 있을 것이라 생각한다.

 

마지막으로, 층 순서도 결정되고 시계방향으로도 돌려준 상태라면 bfs로 0,0,0에서 4,4,4로 갈 수 있는 경로를 탐색한다. 그리고 도착가능하다면 최소 경로를 업데이트 해준다.

이때 답이 12랑 -1만 맞췄었는데 바보같이 0,0,0과 4,4,4가 벽으로 막혀있을 때는 bfs를 바로 탈출시켜야 했는데 그러지 못해서 답이 몇개 틀렸었다....(언제까지 삽질할거니..)

 

코드는 다음과 같다.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
int arr[5][5][5];
int lastarr[5][5][5];
int resultcheck[5];
int ans;
typedef struct Pa{
    int h, r, c;
}P;
int visit[5][5][5];
P queue[1000];
int sp, ep;
int dh[6] = { 0, 0, 0, 0, 1, -1 };    //하, 우, 상, 좌, 아래, 위
int dy[6] = { 1, 0, -1, 0, 0, 0};
int dx[6] = { 0, 1, 0, -1, 0, 0};
int minn(int a, int b) {return a < b ? a : b;}
 
void bfs() {
    if (lastarr[0][0][0] == 0 || lastarr[4][4][4] == 0)
        return;
    sp = ep = 0;
    memset(visit, 0, sizeof(visit));
    visit[0][0][0] = 1;
    P p = { 0,0,0 };
    queue[ep++] = p;
    bool flag = false;
    while (sp < ep) {
        int h = queue[sp].h;
        int r = queue[sp].r;
        int c = queue[sp++].c;
        if (h == 4 && r == 4 && c == 4) {
            flag = true;
            continue;
        }
        for (int k = 0; k < 6; k++) {
            int nh = h + dh[k];
            int ny = r + dy[k];
            int nx = c + dx[k];
            if (nh < 0 || nh>4 || ny < 0 || ny>4 || nx < 0 || nx>4)    continue;
            if (lastarr[nh][ny][nx] == 0)    continue;    //벽일 경우
            if (visit[nh][ny][nx] == 0) {
                visit[nh][ny][nx] = visit[h][r][c] + 1;
                P p2 = { nh, ny, nx };
                queue[ep++] = p2;
            }
        }
    }
    if (flag == true) {
        ans = minn(ans, visit[4][4][4]-1);
    }
}
void make3Dfunc(int a[][5], int b[][5], int c[][5], int d[][5], int e[][5]) {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            lastarr[0][i][j] = a[i][j];
        }
    }
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            lastarr[1][i][j] = b[i][j];
        }
    }
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            lastarr[2][i][j] = c[i][j];
        }
    }
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            lastarr[3][i][j] = d[i][j];
        }
    }
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            lastarr[4][i][j] = e[i][j];
        }
    }
}
void rotation(int idx, int dir, int tmparr[][5]) {    //현재 idx 층을 시계방향으로 한번 회전
    int tmp[5][5];
    //미리 원본 저장
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            tmparr[i][j] = arr[idx][i][j];
        }
    }
    //dir회수 만큼 회전한 결과를 해당 판에 저장해줌
    for (int k = 0; k < dir; k++) {    //dir이 0이면 회전 안함
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                tmp[j][4 - i] = tmparr[i][j];
            }
        }
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                tmparr[i][j] = tmp[i][j];
            }
        }
    }
}
 
int main() {
    register int i, j, k;
 
    for (i = 0; i < 5; i++) {
        for (j = 0; j < 5; j++) {
            for (k = 0; k < 5; k++) {
                scanf("%d", &arr[i][j][k]);
                lastarr[i][j][k] = arr[i][j][k];
            }
        }
    }
    for (i = 0; i < 5; i++) {    // 5개 층 (1,2,3,4,5) 인덱스 저장 (실제쓰일땐 0,1,2,3,4 인덱스로 쓰임)
        resultcheck[i] = i + 1;
    }
    ans = 2e9;
    do {
        //5개 층 모두 섞었으면 시계방향으로 3번 회전하며 조합돌리기
        int tmp1[5][5];
        int tmp2[5][5];
        int tmp3[5][5];
        int tmp4[5][5];
        int tmp5[5][5];
        for (int a = 0; a < 4; a++) {
            rotation(resultcheck[0]-1, a, tmp1);
            for (int b = 0; b < 4; b++) {
                rotation(resultcheck[1]-1, b, tmp2);
                for (int c = 0; c < 4; c++) {
                    rotation(resultcheck[2]-1, c, tmp3);
                    for (int d = 0; d < 4; d++) {
                        rotation(resultcheck[3]-1, d, tmp4);
                        for (int e = 0; e < 4; e++) {
                            rotation(resultcheck[4]-1, e, tmp5);
                            make3Dfunc(tmp1, tmp2, tmp3, tmp4, tmp5);    // lastarr에 다시 3차원으로 합쳐주기
                            bfs();    //bfs로 출발지 부터 탈출지까지 경로 확인하기
                        }
                    }
                }
            }
        }
    } while (next_permutation(resultcheck + 0, resultcheck + 5));
 
    if (ans == 2e9)
        ans = -1;
    printf("%d\n", ans);
    return 0;
}