[BOJ] 16985. Maaaaaaaaaze - Graph/BF/BFS

[BOJ] 16985. Maaaaaaaaaze - Graph/BF/BFS

Problem

제출일 : 2020-02-11

문제 풀이 시간 : 2H

난이도 : ★★★☆

---

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

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

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

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

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

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

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

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

input

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

Output

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

Example

input

1 1 0 0 0
0 0 0 0 1
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 1 1
1 0 0 0 0
0 0 1 0 0
0 0 1 1 1
0 0 1 0 0
0 0 0 0 0
0 0 1 0 1
0 0 0 0 0
0 0 0 1 0
0 0 1 0 1
0 0 1 0 0
1 0 0 0 0
0 0 1 1 0
1 0 1 0 0
0 0 1 0 1
0 0 1 1 0
1 1 0 1 1
0 0 0 0 1
0 1 0 1 0
0 1 0 0 0

output

16

Solution & Inpression

위 문제는 $5 \times 5$의 판 $5$개가 주어진다.

각각의 판을 회전하고 층을 바꾸어 미로를 구성할 수 있다. 미로를 탈출할때 가장 적은 이동횟수를 출력하면 된다.

각각의 판의 층이 바뀌는 경우의 수는 $5!$ 이며 각 판은 $0,90,180,270$도씩 회전해 4개의 상태를 갖을수 있다,

따라서 생성가능한 미로의 수는
$$5! \times 4^5 =75,000‬$$
개의 미로를 생성할 수 있다

생성된 미로를 BFS로 탐색했다 3차원의 x,y,z축에서 각각 +1, -1로 한 칸씩 6방향으로 이동할 수 있다.

---

순열과 중복순열을 이용해 미로의 경우를 구했고 큐를 이용하여 너비우선 탐색을 구현했다.

Code

언어 : JAVA

메모리 : 279,664 kb

실행시간 : 1,176 ms

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int[][][][] map = new int[5][4][5][5];
    static int[] solData = new int[5], goData = new int[5];
    static boolean[] visit = new boolean[5];
    static int ans;
//상하좌우 아래 위
    static int[] dx = { 0, 0, -1, 1, 0, 0 };
    static int[] dy = { -1, 1, 0, 0, 0, 0 };
    static int[] dz = { 0, 0, 0, 0, 1, -1 };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int k = 0; k < 5; k++) {
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    map[k][0][i][j] = sc.nextInt();
                }
            }
            rotateMap(k);
        }

        ans = Integer.MAX_VALUE;

        solve(0); // 각 판의 회전 정도를 결정

        if (ans == Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(ans);
    }

    private static void solve(int depth) {
        if (depth == 5) {
            go(0); // 판의 순서를 결정
            return;
        }
        for (int i = 0; i < 4; i++) {
            solData[depth] = i;
            solve(depth + 1);
        }
    }

    private static void go(int depth) {
        if (depth == 5) {
            calc();
            return;
        }
        for (int i = 0; i < 5; i++) {
            if (!visit[i]) {
                visit[i] = true;
                goData[depth] = i;
                go(depth + 1);
                visit[i] = false;
            }
        }
    }

    private static void calc() {
        int[][][] copy = new int[5][5][5];
        for (int k = 0; k < 5; k++) {
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    copy[k][i][j] = map[goData[k]][solData[k]][i][j];
                }
            }
        }
        // BFS
        // 입구나 출구가 없는 경우
        if (copy[0][0][0] != 1 || copy[4][4][4] != 1)
            return;

        Queue<int[]> q = new LinkedList<>();
        boolean visit[][][] = new boolean[5][5][5];
        q.offer(new int[] { 0, 0, 0, 0 });
        visit[0][0][0] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            // 최저값 보다 클 경우 종료
            if (cur[3] >= ans)
                return;
            // 도착 종료
            if (cur[0] == 4 && cur[1] == 4 && cur[2] == 4) {
                if (ans > cur[3])
                    ans = cur[3];
                return;
            }
            for (int dir = 0; dir < 6; dir++) {
                int nz = cur[0] + dz[dir];
                int ny = cur[1] + dy[dir];
                int nx = cur[2] + dx[dir];
                if (isRange(nz, ny, nx) && !visit[nz][ny][nx] && copy[nz][ny][nx] == 1) {
                    q.offer(new int[] { nz, ny, nx, cur[3] + 1 });
                    visit[nz][ny][nx] = true;
                }
            }
        }
    }

    private static boolean isRange(int nz, int ny, int nx) {
        if (0 <= nz && nz < 5 && 0 <= ny && ny < 5 && 0 <= nx && nx < 5)
            return true;
        return false;
    }

    private static void rotateMap(int k) {
        for (int turn = 1; turn < 4; turn++) {
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    map[k][turn][j][4 - i] = map[k][turn - 1][i][j];
                }
            }
        }
    }
}