[백준 16985번] Maaaaaaaaaze :: 늦깍이 IT

[백준 16985번]  URL Maaaaaaaaaze URL

[전체 소스코드 GitHub에서 확인하기]

1. 두 가지경우에 대한 완전탐색을 실행해야 한다.

2. 우선, 각각의 판의 순서(?)를 정하는 모든 경우의 수를 구해야한다.

A,B,C,D,E 라는 5 x 5 크기의 판이 5개 있을 때, 이 판들을 바닥에서부터 쌓는 순서를 정해야한다.

3. 각각의 판을 쌓아올리는 경우에 대해서 1층부터 5층까지 자리잡은 판들을 각각 0회~3회씩 돌린 후 최단거리를 찾는다.

[시계방향으로 돌리는 메소드]

- prev[][][] 3차원 배열이 있을 때, prev[target][][]의 값들을 시계방향으로 한번 회전시키는 메소드이다.

public static void rotate(int[][][] prev, int target) {
 
        int[][] temp = new int[5][5];
 
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                temp[j][4 - i] = prev[target][i][j];
            }
        }
        for (int i = 0; i < 5; i++)
            prev[target][i] = Arrays.copyOf(temp[i], temp[i].length);
    }

[모든 경우의 수 탐색하기]

numArr[] 배열에는 각각의 칸들을 쌓아올릴 순서가 들어있고, selected[] 배열에는 각 숫자를 조합하기 위한 boolean 값이 들어있다. 맨 아래 For문에서 해당 층에 있는 배열을 0회~3회 돌린 후 다시 DFS() 탐색을 실시한다.

• 1번째 층을 0회전 한 후, DFS 탐색//2번째 층을 0회전 한 후, DFS 탐색//.......//5번째 층을 0회전 한 후, DFS 탐색
• 1번째 층을 0회전 한 후, DFS 탐색//2번째 층을 0회전 한 후, DFS 탐색//.......//5번째 층을 1회전 한 후, DFS 탐색
• 1번째 층을 0회전 한 후, DFS 탐색//2번째 층을 0회전 한 후, DFS 탐색//.......//5번째 층을 2회전 한 후, DFS 탐색
• 1번째 층을 0회전 한 후, DFS 탐색//2번째 층을 0회전 한 후, DFS 탐색//.......//5번째 층을 3회전 한 후, DFS 탐색

public static void dfs(int depth, int[][][] prev) {
 
        if (depth == 5) {
 
            int[][][] reArrange = new int[5][5][5];
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    for (int k = 0; k < 5; k++) {
                        reArrange[i][j][k] = prev[numArr[i]][j][k];
                    }
                }
            }
            ans = Math.min(ans, bfs(reArrange));
            return;
        }
 
        int[][][] temp = new int[5][5][5];
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                for (int k = 0; k < 5; k++) {
                    temp[i][j][k] = prev[i][j][k];
                }
            }
        }
 
        for (int i = 0; i < 5; i++) {
 
            if (!selected[i]) {
                numArr[depth] = i;
                selected[i] = true;
                dfs(depth + 1, temp);
                for (int j = 0; j < 3; j++) {
                    rotate(temp, depth);
                    dfs(depth + 1, temp);
                }
                selected[i] = false;
            }
        }
    }

[탈출하기]

시작점인 (0,0)에서 (4,4)까지 갈 수 있는지 확인한다.

public static int bfs(int[][][] temp) {
 
        if (temp[0][0][0] != 1 || temp[4][4][4] != 1)
            return Integer.MAX_VALUE;
 
        boolean[][][] visited = new boolean[5][5][5];
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(0, 0, 0, 0));
        visited[0][0][0] = true;
 
        while (!q.isEmpty()) {
 
            Node node = q.poll();
            int floor = node.floor;
            int row = node.row;
            int col = node.col;
            int cnt = node.cnt;
 
            if (cnt >= ans)
                return Integer.MAX_VALUE;
 
            if (floor == 4 && row == 4 && col == 4)
                return cnt;
 
            for (int i = 0; i < 6; i++) {
 
                int nf = floor + dirZ[i];
                int nr = row + dirX[i];
                int nc = col + dirY[i];
                if (isBoundary(nf, nr, nc) && !visited[nf][nr][nc] && temp[nf][nr][nc] == 1) {
                    visited[nf][nr][nc] = true;
                    q.offer(new Node(nf, nr, nc, cnt + 1));
                }
            }
        }
        return Integer.MAX_VALUE;
    }