[백준] 16985 Maaaaaaaaaze

 

완전탐색 문제만 주구장창 풀고있다

6방향 탐색으로 풀라는게 뻔히 보이지만 계속 답이 안나왔다

x,y,z를 거꾸로 저장하고 다르게 입력하고 힘이들었다..

코드가 복잡해질수록 잘 안보이니까 함수화를 좀 시켜야겠다

 

먼저 이 문제는 bfs+순열+조합으로 알고있다면 풀 수 있다

각 층을 정하는 방법은 순열을 사용해야한다 => 5!

그리고 몇바퀴 회전을 돌리지는 조합으로 정해야한다 4^5

마지막으로 (0,0,0) -> (4,4,4)의 최단거리를 찾아야한다 => bfs

 

바퀴수는 cnt에 담고 0,1,2,3 바퀴만큼 돌려줬다

 

그리고 나머지는 집중해서 확실하게 코딩하기가 전부다..!

 

순열은 next_permutation을 사용했고 조합은 5중 for문과 백트래킹으로해봤는데

시간이 20ms차이밖에 안난다

 

층을 정할때는 order배열에 넣어서 i번째  판이 order[i]번째 판으로 간다고 생각하면 된다

그렇게 순열로 5! 모든 경우를 다 본다

 

그냥 dfs로 짜는게 편할 것 같다

 

앞으로 코드가 좀 더 길어지더라도 각 기능별로 제대로 함수를 만들어야겠다

 

소스코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int map[11][11][11];
int change_map[11][11][11];
bool check[11][11][11];
int dist[11][11][11];
int dx[6] = {1,-1,0,0,0,0};
int dy[6] = {0,0,1,-1,0,0};
int dz[6] = {0,0,0,0,1,-1};
int order[5]= {0,1,2,3,4};
int cnt[5];
int ans=1e9;
 
bool inner(int x,int y,int z){
    return (0<=x && x<5 && 0<=y && y<5 && 0<=z && z<5);
}
 
void rotate(int num,int op){
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            if(op==0) change_map[order[num]][i][j] = map[num][i][j];
            else if(op==1) change_map[order[num]][i][j]=map[num][4-j][i];
            else if(op==2) change_map[order[num]][i][j]=map[num][4-i][4-j];
            else change_map[order[num]][i][j] = map[num][j][4-i];
        }
    }
}
 
int bfs(){
    if(!change_map[0][0][0] || !change_map[4][4][4]) return 1e9;
 
    memset(check,0,sizeof(check));
    queue<pair<pair<int,int>,int>> q;
    q.push({{0,0},0});
    check[0][0][0]=true;
    dist[0][0][0]=0;
 
    while(!q.empty()){
        int x = q.front().first.first;
        int y = q.front().first.second;
        int z = q.front().second;
        q.pop();
 
        for(int i=0;i<6;i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            int nz = z+dz[i];
            if(inner(nx,ny,nz) && change_map[nz][nx][ny] && !check[nz][nx][ny]){
                check[nz][nx][ny]=true;
                dist[nz][nx][ny]=dist[z][x][y]+1;
                if(nz==4 && nx==4 && ny==4) return dist[4][4][4];
                q.push({{nx,ny},nz});
            }
        }
    }
    return 1e9;
}
 
void solve(int num){
    if(num==5){
        for(int i=0;i<5;i++) rotate(i,cnt[i]);
        ans = min(ans,bfs());
        return;
    }
 
    for(int i=0;i<4;i++){
        cnt[num]=i;
        solve(num+1);
    }
}
 
int main(){
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            for(int k=0;k<5;k++) {
                scanf(" %d",&map[i][j][k]);
            }
        }
    }
 
    do{
       solve(0);
    } while(next_permutation(order,order+5));
    printf("%d\n",(ans==1e9) ? -1 :ans);
}