[BaekJoon] 16985 Maaaaaaaaaze (Java)

1.  문제 링크

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

2.  문제

요약

• 3차원 미로 탈출 대회를 개최하기로 하였는데, 대회의 규칙은 아래와 같습니다.
  • 5 x 5 크기의 판이 5개 주어집니다. 이 중 일부 칸은 참가자가 들어갈 수 있고 일부 칸은 참가자가 들어갈 수 없습니다.
  • 참가자는 주어진 판들을 시계 방향, 혹은 반시계 방향으로 자유롭게 회전할 수 있지만, 판을 뒤집을 수는 없습니다.
  • 회전을 완료한 후, 참가자는 판 5개를 쌓습니다. 판을 쌓는 순서는 참가자가 자유롭게 정할 수 있습니다.
  • 판 5개를 쌓아 만들어진 5 x 5 x 5 크기의 큐브가 참가자를 위한 미로입니다. 이 때, 큐브의 입구는 정육면체에서 참가자가 임의로 선택한 꼭짓점에 위치한 칸이고 출구는 입구와 면을 공유하지 않는 꼭짓점에 위치한 칸입니다.
  • 참가자는 현재 위치한 칸에서 면으로 인접한 칸이 참가자가 들어갈 수 있는 칸인 경우 그 칸으로 이동할 수 있습니다.
  • 참가자 중에서 본인이 설계한 미로를 가장 적은 이동 횟수로 탈출한 사람이 우승합니다. 만약 미로의 입구 혹은 출구가 막혀있거나, 입구에서 출구에 도달할 수 있는 방법이 존재하지 않을 경우에는 탈출이 불가능한 것으로 간주합니다.
• 주어진 판에서 가장 적은 이동 횟수로 출구에 도달할 수 있게끔 미로를 만들었을 때 몇 번 이동을 해야하는지 구하는 문제입니다.
• 입력: 첫 번째 줄부터 25줄에 걸쳐 판이 주어집니다. 각 판은 5줄에 걸쳐 주어지며, 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어집니다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 의미합니다.
• 출력: 첫 번째 줄에 주어진 판으로 설계된 미로를 탈출하는 가장 적은 이동 횟수를 출력합니다. 어떻게 설계하더라도 탈출이 불가능할 경우에는 -1을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static final int SIZE = 5;
    static boolean[][][] maze, copyMaze;
    static boolean[] visited;
    static int[] boardOrder;
    static int answer;

    static void input() {
        Reader scanner = new Reader();

        maze = new boolean[SIZE][SIZE][SIZE];
        copyMaze = new boolean[SIZE][SIZE][SIZE];
        visited = new boolean[SIZE];
        boardOrder = new int[SIZE];

        for(int height = 0; height < SIZE; height++) {
            for(int row = 0; row < SIZE; row++) {
                for(int col = 0; col < SIZE; col++) {
                    int info = scanner.nextInt();
                    if(info == 1) {
                        maze[height][row][col] = true;
                        copyMaze[height][row][col] = true;
                    }
                }
            }
        }
    }

    static void solution() {
        answer = Integer.MAX_VALUE;
        recFunc(0);

        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
    }

    static void recFunc(int boardIdx) {
        if(boardIdx == SIZE) {
            makeMaze(boardOrder);
            rotateMaze(0);
            return;
        }

        for(int idx = 0; idx < SIZE; idx++) {
            if(!visited[idx]) {
                visited[idx] = true;
                boardOrder[boardIdx] = idx;
                recFunc(boardIdx + 1);
                visited[idx] = false;
            }
        }
    }

    static void rotateBoard(int height) {
        boolean[][] temp = new boolean[SIZE][SIZE];
        for(int row = 0; row < SIZE; row++) {
            for(int col = 0; col < SIZE; col++)
                temp[row][col] = copyMaze[height][(SIZE - 1) - col][row];
        }

        System.arraycopy(temp, 0, copyMaze[height], 0, SIZE);
    }

    static void rotateMaze(int height) {
        if(height == SIZE) {
            bfs();
            return;
        }

        rotateMaze(height + 1);

        rotateBoard(height);
        rotateMaze(height + 1);

        rotateBoard(height);
        rotateMaze(height + 1);

        rotateBoard(height);
        rotateMaze(height + 1);

        rotateBoard(height);
    }

    static void bfs() {
        if(!copyMaze[0][0][0]  || !copyMaze[SIZE - 1][SIZE - 1][SIZE - 1]) return;

        int[][] direction = {{0, 0, 1}, {0, 0, -1}, {0, 1, 0}, {0, -1, 0}, {-1, 0, 0}, {1, 0, 0}};
        Queue<Position> queue = new LinkedList<>();
        boolean[][][] visited = new boolean[copyMaze.length][copyMaze[0].length][copyMaze[0][0].length];

        queue.offer(new Position(0, 0, 0, 0));
        visited[0][0][0] = true;

        while(!queue.isEmpty()) {
            Position cur = queue.poll();
            if(cur.h == SIZE - 1 && cur.x == SIZE - 1 && cur.y == SIZE - 1) {
                answer = Math.min(answer, cur.moveNum);
                return;
            }

            for(int dir = 0; dir < direction.length; dir++) {
                int ch = cur.h + direction[dir][0], cx = cur.x + direction[dir][1], cy = cur.y + direction[dir][2];

                if(isInMap(ch, cx, cy)) {
                    if(!visited[ch][cx][cy] && copyMaze[ch][cx][cy]) {
                        visited[ch][cx][cy] = true;
                        queue.offer(new Position(ch, cx, cy, cur.moveNum + 1));
                    }
                }
            }
        }
    }

    static boolean isInMap(int h, int x, int y) {
        if(h >= 0 && h < SIZE && x >= 0 && x < SIZE && y >= 0 && y < SIZE) return true;
        return false;
    }

    static void makeMaze(int[] boardOrder) {
        for(int h = 0; h < SIZE; h++) {
            for(int x = 0; x < SIZE; x++) {
                for(int y = 0; y < SIZE; y++)
                    copyMaze[h][x][y] = maze[boardOrder[h]][x][y];
            }
        }
    }

    static class Position {
        int x, y, h, moveNum;

        public Position(int h, int x, int y, int moveNum) {
            this.x = x;
            this.y = y;
            this.h = h;
            this.moveNum = moveNum;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• boolean 타입의 3차원 배열에 주어진 판의 정보들을 담습니다.
  • 참가자가 들어갈 수 있는 칸을 true, 아닌 칸을 false로 표현합니다.

• 재귀를 통해 5개의 판에 대하여 어떤 순서대로 판을 쌓을지 순서를 정합니다. 나올 수 있는 모든 순서에 대하여 탈출이 가능한지 확인하고 최소 이동 횟수를 구합니다.

static void recFunc(int boardIdx) {
    if(boardIdx == SIZE) {
        makeMaze(boardOrder);
        rotateMaze(0);
        return;
    }

    for(int idx = 0; idx < SIZE; idx++) {
        if(!visited[idx]) {
            visited[idx] = true;
            boardOrder[boardIdx] = idx;
            recFunc(boardIdx + 1);
            visited[idx] = false;
        }
    }
}

• 5개의 판에 대해 순서가 정해졌다면, 해당 순서에 맞게 copyMaze라는 3차원 배열에 5개의 판을 쌓습니다.

static void makeMaze(int[] boardOrder) {
    for(int h = 0; h < SIZE; h++) {
        for(int x = 0; x < SIZE; x++) {
            for(int y = 0; y < SIZE; y++)
                copyMaze[h][x][y] = maze[boardOrder[h]][x][y];
        }
    }
}

• 주어진 5개의 판을 90도로 돌리면서 3차원 미로를 생성하고 미로 생성이 완료되면 BFS를 통해 시작점에서 도착점까지 이동할 수 있는지, 이동할 수 있다면 이동 횟수는 얼마인지 구합니다.
  • 재귀를 이용하여 각 판이 0도, 90도, 180도, 270도로 회전한 모든 경우에 대해 3차원 미로를 생성합니다.

static void rotateMaze(int height) {
    if(height == SIZE) {
        bfs();
        return;
    }

    rotateMaze(height + 1);

    rotateBoard(height);
    rotateMaze(height + 1);

    rotateBoard(height);
    rotateMaze(height + 1);

    rotateBoard(height);
    rotateMaze(height + 1);

    rotateBoard(height);
}

• BFS를 통해 시작점에서 도착점까지 이동이 가능한지 확인합니다.
  • 만약 시작점이나 도착점이 갈 수 없는 곳이라면 이 경우는 탈출이 불가능한 경우이므로 다음 3차원 미로를 확인합니다.
  • 시작점과 도착점 모두 갈 수 있는 곳이라면, BFS를 통해 시작점부터 각 칸을 탐색하며 시작점에서 도착점까지 갈 수 있는지 확인하고 탈출이 가능하다면 answer라는 변수에 더 적은 수의 이동 횟수를 저장합니다.

static void bfs() {
    if(!copyMaze[0][0][0]  || !copyMaze[SIZE - 1][SIZE - 1][SIZE - 1]) return;

    int[][] direction = {{0, 0, 1}, {0, 0, -1}, {0, 1, 0}, {0, -1, 0}, {-1, 0, 0}, {1, 0, 0}};
    Queue<Position> queue = new LinkedList<>();
    boolean[][][] visited = new boolean[copyMaze.length][copyMaze[0].length][copyMaze[0][0].length];

    queue.offer(new Position(0, 0, 0, 0));
    visited[0][0][0] = true;

    while(!queue.isEmpty()) {
        Position cur = queue.poll();
        if(cur.h == SIZE - 1 && cur.x == SIZE - 1 && cur.y == SIZE - 1) {
            answer = Math.min(answer, cur.moveNum);
            return;
        }

        for(int dir = 0; dir < direction.length; dir++) {
            int ch = cur.h + direction[dir][0], cx = cur.x + direction[dir][1], cy = cur.y + direction[dir][2];

            if(isInMap(ch, cx, cy)) {
                if(!visited[ch][cx][cy] && copyMaze[ch][cx][cy]) {
                    visited[ch][cx][cy] = true;
                    queue.offer(new Position(ch, cx, cy, cur.moveNum + 1));
                }
            }
        }
    }
}