백준 16985 (Maaaaaaaaaze) - java

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

16985번: Maaaaaaaaaze

 

문제

평화롭게 문제를 경작하며 생활하는 BOJ 마을 사람들은 더 이상 2차원 미로에 흥미를 느끼지 않는다. 2차원 미로는 너무나 쉽게 탈출이 가능하기 때문이다. 미로를 이 세상 그 누구보다 사랑하는 준현이는 이런 상황을 매우 안타깝게 여겨 아주 큰 상금을 걸고 BOJ 마을 사람들의 관심을 확 끌 수 있는 3차원 미로 탈출 대회를 개최하기로 했다.

대회의 규칙은 아래와 같다.

• 5×5 크기의 판이 5개 주어진다. 이중 일부 칸은 참가자가 들어갈 수 있고 일부 칸은 참가자가 들어갈 수 없다. 그림에서 하얀 칸은 참가자가 들어갈 수 있는 칸을, 검은 칸은 참가자가 들어갈 수 없는 칸을 의미한다.

• 참가자는 주어진 판들을 시계 방향, 혹은 반시계 방향으로 자유롭게 회전할 수 있다. 그러나 판을 뒤집을 수는 없다.

• 회전을 완료한 후 참가자는 판 5개를 쌓는다. 판을 쌓는 순서는 참가자가 자유롭게 정할 수 있다. 이렇게 판 5개를 쌓아 만들어진 5×5×5 크기의 큐브가 바로 참가자를 위한 미로이다. 이 때 큐브의 입구는 정육면체에서 참가자가 임의로 선택한 꼭짓점에 위치한 칸이고 출구는 입구와 면을 공유하지 않는 꼭짓점에 위치한 칸이다.

 

• 참가자는 현재 위치한 칸에서 면으로 인접한 칸이 참가자가 들어갈 수 있는 칸인 경우 그 칸으로 이동할 수 있다.
• 참가자 중에서 본인이 설계한 미로를 가장 적은 이동 횟수로 탈출한 사람이 우승한다. 만약 미로의 입구 혹은 출구가 막혀있거나, 입구에서 출구에 도달할 수 있는 방법이 존재하지 않을 경우에는 탈출이 불가능한 것으로 간주한다.

이 대회에서 우승하기 위해서는 미로를 잘 빠져나올 수 있기 위한 담력 증진과 체력 훈련, 그리고 적절한 운이 제일 중요하지만, 가장 적은 이동 횟수로 출구에 도달할 수 있게끔 미로를 만드는 능력 또한 없어서는 안 된다. 주어진 판에서 가장 적은 이동 횟수로 출구에 도달할 수 있게끔 미로를 만들었을 때 몇 번 이동을 해야하는지 구해보자. 

 

유형 : 순열 + BFS + 구현

 

접근 방식

• 3차원 BFS를 통해 최단 거리를 구하는 문제이다. 고려해야 하는 것은 회전과 배치이다.
• 1층부터 5층까지 내 맘대로 배치하는 방법 : 5 * 4 * 3 * 2 * 1 (순열로 구현)
• 회전 : 시계 방향이든 반시계 방향이든 한 가지 방향으로 4번 수행 ( 4 * 4 * 4 * 4 * 4)

배치

• travel() 메소드를 통해 각 층에 몇번째 원본 배열의 층이 위치할 것인지 분배
• copy() 메소드를 통해 새롭게 배치된 층으로 3차원 배열 구성

    // 순열 백트랙킹
    static void travel(int d){
        if(d == 6){
            int[][][] tmp = copy();
            go(tmp);
            return;
        }

        for(int i=1;i<=5;i++){
            if(!v[i]){
                v[i] = true;
                num[d] = i;
                travel(d + 1);
                v[i] = false;
            }
        }
    }
    
 static int[][][] copy(){
        int[][][] copy = new int[6][6][6];

        for(int i=1;i<=5;i++){
            for(int j=1;j<=5;j++){
                for(int k=1;k<=5;k++){
                	// 새롭게 배치된 층의 2차원 배열을 copy에 복사
                    copy[i][j][k] = board[num[i]][j][k];
                }
            }
        }

        return copy;
    }

 

회전

• rotate() 메소드를 통해 2차원 배열을 반시계 방향으로 회전 : 4번 수행하면 원본으로 돌아옴
• go() 메소드를 통해 5개 층을 4번 돌리는 모든 경우의 수 구현

static void spin(int where,int[][][] board){
        int[][] tmp = new int[6][6];

        for(int i=1;i<=5;i++){
            for(int j=1;j<=5;j++){
                tmp[i][j] = board[where][j][6 - i]; // 반시계 방향으로 회전
            }
        }

        board[where] = tmp;
 }
 
 
 static void go(int[][][] tmp){
        for(int a=1;a<=4;a++){
            spin(1,tmp); // 1번 째 층 회전
            for(int b=1;b<=4;b++){
                spin(2,tmp); // 2번 째 층 회전
                for(int c=1;c<=4;c++){
                    spin(3,tmp); // 3번 째 층 회전
                    for(int d=1;d<=4;d++){
                        spin(4,tmp); // 4번 째 층 회전
                        for(int e=1;e<=4;e++){
                            spin(5,tmp); // 5번 째 층 회전

                            if(tmp[1][1][1] == 0 || tmp[5][5][5] == 0){
                                continue;
                            }

                            bfs(tmp);
                        }
                    }
                }
            }
        }
    }

 

전체 코드

import java.util.*;
import java.io.*;
public class Main {

    static int result = -1;

    static int n = 0;
    static int m = 0;

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

    static int[][][] board;

    static int[] num = new int[6];
    static int[] spinNum = new int[6];
    static boolean[] v= new boolean[6];

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        board = new int[6][6][6];

        for(int i=1;i<=5;i++){

            for(int j=1;j<=5;j++){
                st = new StringTokenizer(bf.readLine(), " ");

                for(int k=1;k<=5;k++){
                    board[i][j][k] = Integer.parseInt(st.nextToken());
                }
            }
        }

        travel(1);
        System.out.println(result);
        bf.close();

    }

    static void tmpPrint(int[][][] board){
        for(int i=1;i<=5;i++){
            for(int j=1;j<=5;j++){
                System.out.print(board[1][i][j]+" ");
            }
            System.out.println();
        }
        System.out.println();
    }

    static int[][][] copy(){
        int[][][] copy = new int[6][6][6];

        for(int i=1;i<=5;i++){
            for(int j=1;j<=5;j++){
                for(int k=1;k<=5;k++){
                    copy[i][j][k] = board[num[i]][j][k];
                }
            }
        }

        return copy;
    }

    static void bfs(int[][][] board){
        int[][][] v = new int[6][6][6];

        Queue<Node> q = new LinkedList<>();
        q.add(new Node(1,1,1));
        v[1][1][1] = 1;

        while(!q.isEmpty()){
            Node cur = q.poll();
            if(cur.x == 5 && cur.y == 5 && cur.z == 5){

                if(result == -1 || result > v[5][5][5] - 1){
                    result = v[5][5][5] - 1;
                    return;
                }
            }


            for(int i=0;i<6;i++){
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                int nz = cur.z + dz[i];

                if(nx < 1 || nx > 5 || ny < 1 || ny > 5 || nz < 1 || nz > 5)
                    continue;

                if(board[nx][ny][nz] == 0)
                    continue;


                if(v[nx][ny][nz] == 0 || v[nx][ny][nz] > v[cur.x][cur.y][cur.z] + 1){
                    v[nx][ny][nz] = v[cur.x][cur.y][cur.z] + 1;
                    q.add(new Node(nx,ny,nz));

                }
            }
        }
    }

    static void spin(int where,int[][][] board){
        int[][] tmp = new int[6][6];

        for(int i=1;i<=5;i++){
            for(int j=1;j<=5;j++){
                tmp[i][j] = board[where][j][6 - i];
            }
        }

        board[where] = tmp;
    }

    static void print(int[][][] board){
        for(int i=1;i<=5;i++){
            for(int j=1;j<=5;j++){
                for(int k=1;k<=5;k++){
                    System.out.print(board[i][j][k]+" ");
                }
                System.out.println();
            }
            System.out.println();
        }
    }

    static void go(int[][][] tmp){
        for(int a=1;a<=4;a++){
            spin(1,tmp);
            for(int b=1;b<=4;b++){
                spin(2,tmp);
                for(int c=1;c<=4;c++){
                    spin(3,tmp);
                    for(int d=1;d<=4;d++){
                        spin(4,tmp);
                        for(int e=1;e<=4;e++){
                            spin(5,tmp);

                            if(tmp[1][1][1] == 0 || tmp[5][5][5] == 0){
                                continue;
                            }

                            bfs(tmp);
                        }
                    }
                }
            }
        }
    }


    static void travel(int d){
        if(d == 6){
            int[][][] tmp = copy();
            go(tmp);
            return;
        }

        for(int i=1;i<=5;i++){
            if(!v[i]){
                v[i] = true;
                num[d] = i;
                travel(d + 1);
                v[i] = false;
            }
        }
    }
}
class Node{
    int x;
    int y;

    int z;

    Node(int x,int y,int z){
        this.x = x;
        this.y = y;
        this.z = z;
    }
}