[백준OJ] 16985번 Maaaaaaaaaze - Java

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

16985번: Maaaaaaaaaze

---

풀이

모든 경우의수를 다 대입해서 탐색했습니다.

순서에 대한 모든 경우를 결정한 뒤, 결정된 배열의 각 층을 모두 돌려서 모든 경우를 구한 뒤, BFS를 통해 최소경로를 찾았습니다. 

이때 어차피 모든 경우의 수를 다 탐색하기때문에, 임의로 입구를 (0,0,0), 출구를 (4,4,4)로 고정해도 문제가 해결됩니다.

시간복잡도

순서를 정하는 경우의 수 O(5!), 각 순서를 정한 뒤, 모든층에 대해 회전하는 경우의 수 O(4*4*4*4*4) , BFS O(5*5*5) 기 때문에, 최종 경우의 수는 O(5! * 4^5 * 5^3) 이 됩니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int[][][] maze = new int[5][5][5];
    static int[][][] copy = new int[5][5][5];

    static boolean[] visited = new boolean[5];
    static int answer = Integer.MAX_VALUE;
    static int[][] mv = new int[][]{{0, 0, 1}, {0, 0, -1}, {0, 1, 0}, {0, -1, 0}, {1, 0, 0}, {-1, 0, 0}};

    public static class Node {
        int x, y, z;

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

    public static boolean isIn(int x, int y, int z) {
        return 0 <= x && x < 5 && 0 <= y && y < 5 && 0 <= z && z < 5;
    }

    public static void bfs() {
        if (copy[0][0][0] == 0) {
            return;
        }

        Queue<Node> q = new LinkedList<>();
        int[][][] dist = 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++) {
                    dist[i][j][k] = Integer.MAX_VALUE;
                }
            }
        }

        q.offer(new Node(0, 0, 0));
        dist[0][0][0] = 0;

        while (!q.isEmpty()) {
            Node node = q.poll();
            int x = node.x;
            int y = node.y;
            int z = node.z;
            int d = dist[x][y][z];

            if (x == 4 && y == 4 && z == 4) {
                answer = Math.min(answer, dist[x][y][z]);
                return;
            }
            for (int dd = 0; dd < mv.length; dd++) {
                int nx = x + mv[dd][0];
                int ny = y + mv[dd][1];
                int nz = z + mv[dd][2];
                if (isIn(nx, ny, nz) && dist[nx][ny][nz] > d + 1 && copy[nx][ny][nz] == 1) {
                    q.offer(new Node(nx, ny, nz));
                    dist[nx][ny][nz] = d + 1;
                }
            }
        }
    }

    public static void dfs(int index) {
        if (index == 5) {
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    for (int k = 0; k < 4; k++) {
                        for (int l = 0; l < 4; l++) {
                            for (int m = 0; m < 4; m++) {
                                bfs();
                                copy[4] = turn(copy[4]);
                            }
                            copy[3] = turn(copy[3]);
                        }
                        copy[2] = turn(copy[2]);
                    }
                    copy[1] = turn(copy[1]);
                }
                copy[0] = turn(copy[0]);
            }
            return;
        }

        for (int i = 0; i < 5; i++) {
            if (visited[i]) continue;

            visited[i] = true;
            for (int x = 0; x < 5; x++) {
                for (int y = 0; y < 5; y++) {
                    copy[index][x][y] = maze[i][x][y];
                }
            }
            dfs(index + 1);
            visited[i] = false;
        }
    }


    public static int[][] turn(int[][] maze) {
        int[][] cp = new int[5][5];

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                cp[i][j] = maze[5 - j - 1][i];
            }
        }
        return cp;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int k = 0; k < 5; k++) {
                    maze[i][j][k] = Integer.valueOf(st.nextToken());
                }
            }
        }

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

    }
}