[Baekjoon] 16985: Maaaaaaaaaze

문제

아... 너무 길다

다음 링크를 통해 자세한 내용을 확인해보자.

[Baekjoon] 16985: 매애애애애애애애애즈

16985번: Maaaaaaaaaze

 

3차원 미로 찾기 문제이다.

여기서 조건은 다음과 같다.

1. 판은 회전할 수 있다.
2. 판은 순서가 바뀔 수 있다.
3. 꼭짓점이면서 1인 곳으로만 들어갈 수 있다.
4. 정반대 꼭짓점으로만 나올 수 있다.

위를 고려하면서 풀면 그냥 풀린다.

얼마나 쉬웠으면,,,^^

스터디원 모두 막판 원큐 세레모니를 보여주고 있다.

 

풀이

내 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;

public class Q16985 {

    private static int[][][] map;
    private static int[][][] newMap;
    private static boolean[] visited;
    private static int[] order;
    private static int[][] directions = {
            {0, 0, 1},
            {0, 1, 0},
            {0, -1, 0},
            {0, 0, -1},
            {-1, 0, 0},
            {1, 0, 0}
    };

    private static int count = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        map = new int[5][5][5];
        newMap = new int[5][5][5];
        order = new int[5];
        visited = new boolean[5];
        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++) {
                    map[i][j][k] = Integer.parseInt(st.nextToken());
                }
            }
        }

        perm(0);
        search(0);

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

    public static void perm(int cur) {
        if (cur == 5) {
            search(0);
            return;
        }

        for (int i = 0; i < 5; i++) {
            if (visited[i]) {
                continue;
            }
            order[cur] = i;
            visited[i] = true;
            perm(cur + 1);
            visited[i] = false;
        }
    }

    public static void search(int cur) {
        if (cur == 5) {
            if (newMap[0][0][0] == 1) {
                count = Math.min(count, bfs(new int[]{0, 0, 0}));
            }
            if (newMap[0][4][0] == 1) {
                count = Math.min(count, bfs(new int[]{0, 4, 0}));
            }
            if (newMap[0][0][4] == 1) {
                count = Math.min(count, bfs(new int[]{0, 0, 4}));
            }
            if (newMap[0][4][4] == 1) {
                count = Math.min(count, bfs(new int[]{0, 4, 4}));
            }
            return;
        }

        for (int i = 0; i < 4; i++) {
            rotate(cur, order[cur], i);
            search(cur + 1);
        }
    }

    public static void rotate(int index, int cur, int rot) {
        if (rot == 0) {
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    newMap[index][i][j] = map[cur][i][j];
                }
            }
            return;
        }
        if (rot == 1) {
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    newMap[index][j][4 - i] = map[cur][i][j];
                }
            }
            return;
        }
        if (rot == 2) {
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    newMap[index][4 - i][4 - j] = map[cur][i][j];
                }
            }
            return;
        }

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                newMap[index][4 - j][i] = map[cur][i][j];
            }
        }
    }

    public static int bfs(int[] start) {
        Deque<int[]> dq = new ArrayDeque<>();
        boolean[][][] visited = new boolean[5][5][5];
        dq.offerLast(new int[]{start[0], start[1], start[2], 0});
        visited[start[0]][start[1]][start[2]] = true;

        while (!dq.isEmpty()) {
            int[] cur = dq.pollFirst();
            for (int[] direction : directions) {
                int upDown = direction[0] + cur[0];
                int row = direction[1] + cur[1];
                int col = direction[2] + cur[2];

                if (upDown < 0 || upDown >= 5 || row < 0 || row >= 5 || col < 0 || col >= 5) {
                    continue;
                }

                if (newMap[upDown][row][col] == 0) {
                    continue;
                }

                if (visited[upDown][row][col]) {
                    continue;
                }

                if (upDown == 4) {
                    if ((start[1] == 4 && row == 0) || (start[1] == 0 && row == 4)) {
                        if ((start[2] == 4 && col == 0) || (start[2] == 0 && col == 4)) {
                            return cur[3] + 1;
                        }
                    }
                }
                visited[upDown][row][col] = true;
                dq.offerLast(new int[]{upDown, row, col, cur[3] + 1});
            }
        }
        return Integer.MAX_VALUE;
    }
}

너무 길다. 간략히 설명하자면

1. 숫자 조합을 구한다.
2. 숫자 조합대로 진행하는데 4번의 회전상황을 모두 고려하며 진행한다.
   • 즉, 4 3 2 5 1 이라고 하면 4(상하좌우) 5(상하좌우) ... 이렇게 진행한다.
3. 그 후 bfs로 탐색하면서 진입한 곳의 반대편 꼭짓점에 도달한다
4. 탈^출^

 

회고

왜 이 문제를 냈는지 기억이 안난다.