[백준][C++] 16985 Maaaaaaaaaze

www.acmicpc.net/problem/16985

16985번: Maaaaaaaaaze

 

 

 

알고리즘 종류

    - 구현

 

 

 

사고 과정

    1. [5][5] 모양을 판을 5층 쌓아야 한다. 쌓는 방법을 알기 위해서 DFS로 조합을 구한다.

    2. 조합을 알게 되면, 각 층의 판을 돌려보아야 한다. 돌리는 것은 총 4*4*4*4*4의 경우이다.

        2-1. 어떻게 돌리는지는 for문을 4개 사용한다.

        2-2. 어떻게 돌리는지 알았다면, 원본 mat에서 복사 배열인 mat2로 돌린 값을 옮긴다.

    3. 돌린 mat2를 알게 되었다면, [0][0][0]에서 출발하여 [4][4][4]로 BFS를 사용하여 이동한다.

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
 
using namespace std;
 
// 움직이는 사람
struct Person{
    int h, y, x, dist=0;
};
 
int mat[5][5][5];
int mat2[5][5][5];
int stack[5];
int isVisited[5];
int isVisited2[5][5][5];
int dir[6][3] = {{0,0,1}, {0,1,0}, {0,0,-1}, {0,-1,0}, {1,0,0}, {-1,0,0}};
 
int answer = 987654321;
 
 
bool isValid(int h, int y, int x){
    return (h>=0 && h<5) && (y>=0 && y<5) && (x>=0 && x<5);
}
 
// 0이면 제자리, 1이면 시계방향 90도, 2이면 시계방향 180도, 3이면 반시계방향 90도
void rotate(int a, int b, int c, int d, int e){
    int cmd[5];
    cmd[0]=a;
    cmd[1]=b;
    cmd[2]=c;
    cmd[3]=d;
    cmd[4]=e;
 
    for(int l=0; l<5; l++){
        // 복사될 mat2에 0~4 차례대로 쌓기
        // 쌓아질 판은 mat의 lev에 있는 판
        // 회전 명령은 cmd에서 가져온다.
        int lev = stack[l];
        int com = cmd[l];
        
        if(com==0){
            for(int i=0; i<5; i++){
                for(int j=0; j<5; j++){
                    mat2[l][i][j] = mat[lev][i][j];
                }
            }
        }
        else if(com==1){
            for(int i=0; i<5; i++){
                for(int j=0; j<5; j++){
                    mat2[l][j][4-i] = mat[lev][i][j];
                }
            }
        }
        else if(com==2){
            for(int i=0; i<5; i++){
                for(int j=0; j<5; j++){
                    mat2[l][4-i][4-j] = mat[lev][i][j];
                }
            }
        }
        else if(com==3){
            for(int i=0; i<5; i++){
                for(int j=0; j<5; j++){
                    mat2[l][4-j][i] = mat[lev][i][j];
                }
            }
        }
    }
}
 
// 2차원에서 BFS를 하듯이 하면 된다.
int move(){
    if(mat2[0][0][0] == 0) return -1; // 시작점이 0이면 출발할 수 없다.
    memset(isVisited2, 0, sizeof(isVisited2));
    queue<Person> q;
    Person p;
    p.h=0;
    p.y=0;
    p.x=0;
    p.dist=0;
    q.push(p);
    
    isVisited2[0][0][0] = 1;
    
    while(!q.empty()){
        
        int size = q.size();
        
        for(int i=0; i<size; i++){
            int h = q.front().h;
            int y = q.front().y;
            int x = q.front().x;
            int dist = q.front().dist;
            q.pop();
            
            if(h==4 && y==4 && x==4) return dist;
        
            for(int d=0; d<6; d++){
                int nh = h + dir[d][0];
                int ny = y + dir[d][1];
                int nx = x + dir[d][2];
            
                if(!isValid(nh, ny, nx)) continue;
                if(mat2[nh][ny][nx] == 0) continue;
                if(isVisited2[nh][ny][nx]) continue;
                
                isVisited2[nh][ny][nx] = 1;
                
                Person pp;
                pp.h=nh;
                pp.y=ny;
                pp.x=nx;
                pp.dist=dist+1;
                
                q.push(pp);
                
            }    
        }
    }
    return -1;
}
 
// 회전은 5개 층에 대한 모든 경우를 고려한다.
void maze_rotate(){
    for(int a=0; a<4; a++){
        for(int b=0; b<4; b++){
            for(int c=0; c<4; c++){
                for(int d=0; d<4; d++){
                    for(int e=0; e<4; e++){
                        // 회전시킨다.
                        rotate(a, b, c, d, e);
                        int dist = move();
                        if(dist < answer && dist != -1) answer = dist;
                    }
                }
            }
        }
    }
}
 
 
void dfs(int cnt){
    // 판을 놓을 위치를 찾았으면, 회전시키기
    if(cnt == 5){
        maze_rotate();
        return;
    }
    
    for(int i=0; i<5; i++){
        if(isVisited[i]) continue;
        isVisited[i] = 1;
        stack[cnt] = i;
        dfs(cnt+1);
        stack[cnt] = 0;
        isVisited[i] = 0;
    }
}
 
 
void solution(){
    // 어떤 층에 무슨 판을 놓을지 조합으로 찾기
    dfs(0);
    if(answer == 987654321) cout << -1;
    else cout << answer << endl;
}
 
 
int main(void){
    for(int i=0; i<5; i++){
        for(int j=0; j<5; j++){
            for(int k=0; k<5; k++){
                cin >> mat[i][j][k];
            }
        }
    }
    
    solution();
}

 

 

 

시행착오

    - 문제에서 '임의로 선택한 꼭짓점에 위치한 칸이고 출구는 입구와 면을 공유하지 않는 꼭짓점에 위치한 칸이다.'라고 언급해서, 본인은 회전이 완료된 mat2의 상단 4개의 꼭지점에서 하단 4개의 꼭지점으로 가는 4가지 경우를 생각했다. 그래서 BFS를 4번 해야하는 줄 알았다. 그런데 시간이 너무 그려서 생각해보니 굳이 4번 할 필요가 없었다. 왜냐하면, 판은 회전하기 때문에 한 꼭지점에서만 해도 된다.

    - mat에 손대서 고생했다. mat은 원본 값을 가진 배열이다. 이 배열을 손대면 안 되었는데, rotate()에서 실수로 mat을 건들게 되었다.

    - 시작점 [0][0][0]이 0이면 이동을 할 수 없다는 것을 고려하지 못했다. 이것을 눈치챈 계기는 테스트 케이스를 넣어보는데 -1이 나오는 테스트 케이스를 제외하고 모두 최단 이동거리만 나오는 것이었다. 모두 12만 나와서 너무 이상해서 오랜 시간동안 살펴본 결과 시작점을 고려했어야 했다. 굉장히 기본적인 조건이었지만, 꼼꼼하지 못한 태도로 놓치게 되어 많은 시간을 낭비하게 되었다. 조건을 리스트로 만들어야겠다.