[Algorithm] 백준/16985 :: Maaaaaaaaaze

* 핵심

문제를 하루종일 삽질하면서 풀었다.

첫번째 실수는 문제를 이해를 잘못해서 각 미로를 nCr로 조합한다는 경우를 생각하지 못했고, 

두번째 실수는 visited를 매번 초기화하지 않아서 한바퀴밖에 돌지않는 경우가 발생했다.

문제를 뜯어보면 3가지 역할로 분리할 수 있다.

1. nCr 함수 : 판을 쌓는 순서를 참가자가 자유롭게 정할 수 있으므로 5!의 경우의 수가 발생

2. Rotation(DFS) 함수 : 판을 돌리는 경우의 수는 총 4가지이므로 4^5(판의 개수) 의 경우의 수 발생 >> DFS로 경우의 수 찾기

3. BFS 함수 : Rotaion으로 받은 map을 가지고 0,0,0에서 4,4,4로 가는 경우의 수를 찾는 함수

문제를 위처럼 3단계로 나누고 실수없이 구현하면 금방 풀 수 있는 문제였다.

특히, 자바는 파라미터가 Call by Reference이기 때문에 DFS 함수를 호출하고 다시 값을 변경해주는 것 또한 잊지말아야 한다.

* 문제

문제

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

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

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

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

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

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

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

입력

첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 의미한다.

출력

첫째 줄에 주어진 판으로 설계된 미로를 탈출하는 가장 적은 이동 횟수를 출력한다. 단, 어떻게 설계하더라도 탈출이 불가능할 경우에는 -1을 출력한다.

* 소스 코드

import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int[][][] map = new int[5][5][5];
    public static boolean[][][] visited = new boolean[5][5][5];
    public static int[] p = {0, 0, 0, 0, 0};        //nCr로 순서를 정할 때 idx를 저장하는 배열
    public static int[] dx = {1, -1, 0, 0, 0, 0};
    public static int[] dy = {0, 0, 1, -1, 0, 0};
    public static int[] dh = {0, 0, 0, 0, 1, -1};
    public static int ans = Integer.MAX_VALUE;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < 5; i++) {                //높이
            for (int j = 0; j < 5; j++) {            //가로
                stk = new StringTokenizer(br.readLine());
                for (int k = 0; k < 5; k++) {        //세로
                    map[i][j][k] = Integer.parseInt(stk.nextToken());
                }
            }
        }
        nCr(0, new boolean[5]);
        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
    }
 
    //참가자가 5개의 판을 쌓는 5!의 경우의 수
    public static void nCr(int cnt, boolean[] visited) {
        if (cnt == 5) {        //경우의 수를 찾았을때마다 만든 배열을 가지고 Backtracking 함수 호출
            int[][][] nmap = new int[5][5][5];
            for (int i = 0; i < 5; i++) {
                int idx = p[i];
                for (int x = 0; x < 5; x++) {
                    for (int y = 0; y < 5; y++) {
                        nmap[i][x][y] = map[idx][x][y];
                    }
                }
            }
            Backtracking(0, new int[5][5][5], nmap);
            return;
        }
        for (int i = 0; i < 5; i++) {
            if (!visited[i]) {
                visited[i] = true;
                p[i] = cnt;
                nCr(cnt + 1, visited);
                p[i] = 0;
                visited[i] = false;
            }
        }
        return;
    }
 
    //dfs를 이용하여 각 높이별 회전할 때의 저장배열
    public static void Backtracking(int height, int[][][] nmap, int[][][] map) {
        if (height == 5) {        //배치한 판을 회전시킨 경우의 수마다 bfs 
            if (nmap[0][0][0] == 1 && nmap[4][4][4] == 1) {
                int tmp = bfs(nmap);
                if (tmp != -1) ans = Math.min(ans, tmp);
            }
            return;
        }
        for (int cnt = 1; cnt <= 4; cnt++) {     //반시계 돌리는 횟수
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    if (map[height][i][j] == 1) {
                        switch (cnt) {
                            case 1:
                                nmap[height][j][4 - i] = 1;
                                break;
                            case 2:
                                nmap[height][4 - i][4 - j] = 1;
                                break;
                            case 3:
                                nmap[height][4 - j][i] = 1;
                                break;
                            case 4:
                                nmap[height][i][j] = 1;
                                break;
                        }
                    }
                }
            }
            Backtracking(height + 1, nmap, map);
            nmap[height] = new int[5][5];
        }
        return;
    }
 
    //bfs를 이용해서 저장된 nmap을 가지고 정점가능횟수 찾는 횟수
    public static int bfs(int[][][] nmap) {
        Queue<Point> q = new LinkedList<>();
        visited = new boolean[5][5][5];
        q.add(new Point(0, 0, 0, 0));
        while (!q.isEmpty()) {
            Point p = q.poll();
            if (p.height == 4 && p.x == 4 && p.y == 4) return p.cnt;
            if (!visited[p.height][p.x][p.y]) {
                visited[p.height][p.x][p.y] = true;
                for (int k = 0; k < 6; k++) {
                    int nh = p.height + dh[k];
                    int nx = p.x + dx[k];
                    int ny = p.y + dy[k];
                    if (check(nh, nx, ny) && nmap[nh][nx][ny] == 1 && !visited[nh][nx][ny]) {
                        q.add(new Point(nh, nx, ny, p.cnt + 1));
                    }
                }
            }
        }
        return -1;
    }
 
    public static boolean check(int h, int x, int y) {
        if (h >= 0 && h < 5 && x >= 0 && x < 5 && y >= 0 && y < 5) return true;
        return false;
    }
 
    public static class Point {
        int height, x, y, cnt;
 
        public Point(int height, int x, int y, int cnt) {
            this.height = height;
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
}