[BOJ] Maaaaaaaaaze

난이도 : Gold 2

문제링크

• 5*5 격자판이 5개 쌓인 3차원 미로가 존재한다 (5*5*5)
• 주어진 5개의 격자판을 임의의 순서대로 쌓아 퍼즐을 만든다.
• 맨 위 격자의 좌측 상단(0, 0)에서 맨 아래 격자의 우측 하단까지(4, 4) 도착하는데 걸리는 최단 이동 횟수를 구하라

 

• 격자는 회전가능하며, 벽은 이동할 수 없음

 

해설

전체코드 보기

1. 퍼즐을 만들 수 있는 모든 경우 탐색하기

private static void dfs(int depth, int[][][] curMaze) {
    if (depth == height) {
        if (curMaze[0][0][0] == 1 && curMaze[4][4][4] == 1) {
            int turn = bfs(curMaze, new boolean[height][rows][cols]);
            if (turn == 12) {
                findAnswer = true;
                answer = 12;                    
            } else if (turn > -1) {
                answer = Math.min(answer, turn);
            }                        
        }
        return;
    }

    for (int i = 0; i < height; i++) {
        if (!check[i]) {
            check[i] = true;
            for (int j = 0; j < 4 && !findAnswer; j++) {
                if (j == 0)      curMaze[depth] = maze[i];
                else if (j == 1) curMaze[depth] = rotate90(maze[i]);
                else if (j == 2) curMaze[depth] = rotate180(maze[i]);
                else if (j == 3) curMaze[depth] = rotate270(maze[i]);

                dfs(depth+1, curMaze);
            }
            curMaze[depth] = maze[i];
            check[i] = false;            
        }            
    }
}

• 5개의 격자를 이용하여 만들 수 있는 모든 퍼즐의 경우의 수를 재귀적으로 DFS를 구현하여 탐색합니다.
  • 현재 방문한 높이에서 이전에 사용되지 않은 격자라면 어느것이라도 올 수 있다.
  • 현재 방문한 높이에서 사용된 격자가 회전되는 경우도 체크되어야 한다.
  • 격자를 깊이탐색하면서 기록하는데 쓰인 check, curMaze 배열을 탐색 후 다음 탐색에 영향을 주지 않도록 백트래킹
    • check : 다음 깊이에서 탐색할 수 없는 격자는 이전에 쓰였던 격자이므로 방문 처리용을 사용한다.
    • curMaze : 깊이 탐색을 통해 만들어지는 퍼즐이므로 회전하였던 격자를 원본의 격자로 되돌려준다.
• 격자의 출발점과 도착점이 각각 첫번째 맨 왼쪽상단과 마지막 맨 오른쪽 하단 이므로 (0,0,0) (4,4,4) 는 벽이 아니여야 한다.
• 각 경우에서 (0,0,0) 부터 (4,4,4) 까지 너비탐색을 통해 최단거리로 도착하는 비용을 얻는다.
  • 모든 경우에서 최소비용을 얻어야 하므로 최소 비용을 너비탐색마다 갱신해준다.
  • 5*5*5에서 출발지에서 도착치까지 가는데 가장 최소 비용인 12를 얻으면, 더 이상 깊이탐색을 할 필요가 없다.

 

2. 격자 회전하기

격자를 시계방향으로 90도씩 회전할 경우, 총 세가지 경우의 격자가 발생합니다.

 

90도 회전

private static int[][] rotate90(int[][] maze) {
    int rows = maze.length, cols = maze[0].length;
    int[][] rotatedMaze = new int[cols][rows];
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            rotatedMaze[j][rows-1-i] = maze[i][j];
        }
    }        
    return rotatedMaze;
}

• 격자의 높이와 폭 사이즈가 뒤바뀝니다.
• 각각의 좌표가 회전됩니다.
  • x -> y
  • y -> width - 1 - x

 

 

180도 회전

private static int[][] rotate180(int[][] maze) {
    int rows = maze.length, cols = maze[0].length;
    int[][] rotatedMaze = new int[rows][cols];
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            rotatedMaze[rows-1-i][cols-1-j] = maze[i][j];
        }
    }
    return rotatedMaze;
}

• 격자의 높이와 폭 사이즈는 그대로입니다.
• 각각의 좌표가 회전됩니다.
  • x -> width - 1 - x
  • y -> width - 1 - y

 

 

270도 회전

private static int[][] rotate270(int[][] maze) {
    int rows = maze.length, cols = maze[0].length;
    int[][] rotatedMaze = new int[cols][rows];
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            rotatedMaze[cols-1-j][i] = maze[i][j];
        }
    }        
    return rotatedMaze;
}

• 격자의 높이와 폭 사이즈가 뒤바뀝니다.
• 각각의 좌표가 회전됩니다.
  • x -> width - 1 - y
  • y -> x

 

3. 퍼즐의 출발지부터 도착지까지 도착하는 최소비용 얻기

private static int bfs(int[][][] curMaze, boolean[][][] visited) {
    Queue<Node> queue = new LinkedList<>();
    queue.offer(new Node(0, 0, 0, 0));
    visited[0][0][0] = true;

    while (!queue.isEmpty()) {
        Node cn = queue.poll();
        int cz = cn.z, cy = cn.y, cx = cn.x, ct = cn.turn;
        if (cz == height-1 && cy == rows-1 && cx == cols-1) return ct;

        for (int[] dir : dirs) {
            int nz = cz + dir[0], ny = cy + dir[1], nx = cx + dir[2], nt = ct + 1;
            if (validate(nz, ny, nx, curMaze, visited)) {
                visited[nz][ny][nx] = true;
                queue.offer(new Node(nz, ny, nx, nt));
            }
        }
    }

    return -1;
}

• (0,0,0)에서 (4,4,4)까지 이동하는데 드는 최소비용을 얻기 위해 큐를 활용한 BFS 탐색을 실행합니다.
• 다음 방문의 자격이 있는 좌표를 큐에 넣어 큐가 비어있을때까지 반복합니다

 

private static boolean validate(int z, int y, int x, int[][][] curMaze, boolean[][][] visited) {
    if (z < 0 || z >= height || y < 0 || y >= rows || x < 0 || x >= cols) return false;
    if (curMaze[z][y][x] == 0) return false;
    if (visited[z][y][x]) return false;
    return true;
}

• 큐에 들어가려는 좌표의 유효성 체크
  • 퍼즐의 범위 안에있는 좌표인지 확인
  • 방문하려는 좌표가 벽이 아닌지 확인
  • 이전에 방문하지 않았던 좌표인지 확인