16985

백준 16985번

Link: 16985번: Maaaaaaaaaze

---

문제 설명

아아아아아아아아주 지저분한 형태의 BFS 문제다.

예전 삼성 코딩테스트 볼때부터 큐브문제는 정말 싫었는데, 이문제는 큐브 돌리기에 BFS까지 추가된 형태.

생각보다 푸는방법은 간단했다.

우선 입력을 받고 나서, 큐브의 각 층을 회전시킬 수 있는 모든 경우에 대해 회전시킨다.

그 다음, 회전된 각 층을 순열을 통해 재배열한다.

이렇게 재배열까지 완료한 지도를 BFS를 통해 탐색하고 최단거리를 찾으면 되는 문제다.

풀어보고 나니 모든 경우 다 따지고 BFS 돌린다는 단순한 풀이인데, 구현이 좀 많이 복잡한편이다.

회전하는 모든 경우 따질때 5중 for문을 쓰는데, 이걸 써도 통과가 될까 했는데 되더라.

아주 단순무식하게 모든 경우를 빠짐없이 따져보면 결과가 잘 나오고, 시간초과에 대해서도 딱히 걱정할필요가 없는 문제였다.

코드가 좀 기니 읽는데 주의할것…

---

정답 코드

//
// Created by Keith_Lee on 25/03/2019.
//

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

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

int map[5][5][5] = {0, };
int setMap[5][5][5] = {0, };

int dx[] = {0, 0, 0, 0, 1, -1};
int dy[] = {0, 0, 1, -1, 0, 0};
int dz[] = {1, -1, 0, 0, 0, 0};

int result = 99999999;

void rotate(int partIndex, int degree){ // 몇층을 몇도로 돌릴것인가
    if(degree == 0){
        return;
    }

    int temp[5][5] = {0, };
    memcpy(temp, setMap[partIndex], sizeof(int) * 25);

    if(degree == 1){ // 오른쪽으로 90도
        for(int i=0; i<5; i++){
            for(int j=0; j<5; j++){
                setMap[partIndex][i][j] = temp[4-j][i];
            }
        }
    }
    else if(degree == 2){ // 오른쪽으로 180도
        for(int i=0; i<5; i++){
            for(int j=0; j<5; j++){
                setMap[partIndex][i][j] = temp[4-i][4-j];
            }
        }
    }
    else if(degree == 3){ // 오른쪽으로 270도
        for(int i=0; i<5; i++){
            for(int j=0; j<5; j++){
                setMap[partIndex][i][j] = temp[j][4-i];
            }
        }
    }
}

int BFS(){
    queue<Point> Queue;
    bool visit[5][5][5] = {false, };

    Queue.push({0, 0, 0});
    visit[0][0][0] = true;
    int distance = 0;

    while(!Queue.empty()){
        vector<Point> points;

        while(!Queue.empty()){
            points.push_back(Queue.front());
            Queue.pop();
        }

        for(int v=0; v<points.size(); v++){
            int currentZ = points[v].z;
            int currentX = points[v].x;
            int currentY = points[v].y;

            if(currentZ == 4 && currentX == 4 && currentY == 4){
                return distance;
            }

            for(int i=0; i<6; i++){
                int nextZ = currentZ + dz[i];
                int nextX = currentX + dx[i];
                int nextY = currentY + dy[i];

                if(nextX >= 0 && nextX < 5 && nextY >= 0 && nextY < 5 && nextZ >= 0 && nextZ < 5){
                    if(!visit[nextZ][nextX][nextY] && setMap[nextZ][nextX][nextY] == 1){
                        visit[nextZ][nextX][nextY] = true;
                        Queue.push({nextZ, nextX, nextY});
                    }
                }
            }
        }

        distance++;
    }

    return -1;
}

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];
            }
        }
    }

    vector<int> perm = {0, 1, 2, 3, 4};

    do{
        for(int i=0; i<4; i++){
            for(int j=0; j<4; j++){
                for(int k=0; k<4; k++){
                    for(int l=0; l<4; l++){
                        for(int m=0; m<4; m++){
                            for(int n=0; n<5; n++){
                                memcpy(setMap[n], map[perm[n]], sizeof(int) * 25);
                            } // 바꾼 맵 초기화: 순열로 순서 배정

                            rotate(0, i);
                            rotate(1, j);
                            rotate(2, k);
                            rotate(3, l);
                            rotate(4, m);
                            // 각층 회전

                            if(setMap[0][0][0] == 1 && setMap[4][4][4] == 1){
                                int temp = BFS();

                                if(temp > 0 && result > temp){
                                    result = temp;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    while(next_permutation(perm.begin(), perm.end()));

    if(result == 99999999){
        result = -1;
    }
    cout << result << '\n';

    return 0;
}

---