[백준/Java] #16985 Maaaaaaaze

Maaaaaaze (16985번)

사용 언어 : Java
레벨 : 골드2
📎 https://www.acmicpc.net/problem/16985

16985번: Maaaaaaaaaze

 

❓ 접근

조건이 굉장히 많고 번거로워서 문제를 완전히 이해하는데 시간이 좀 걸렸다.

 

1. 백트래킹을 이용해 5개의 판의 쌓을 순서를 정한다. (순열)

2. 백트래킹을 이용해 각 판의 회전방향을 정한다. (중복순열)

3. 순서대로 회전방향에 맞게 판을 쌓는다.

4. 입구와 출구가 1일 경우 BFS를 돌린다.

5. 출구에 도착했을 때, 최단 거리 12일 경우 시스템을 종료하고 아니면 모든 경우의 수를 돌려 최솟값을 저장하고 마지막에 최솟값을 출력한다.

 

솔직히 시간만 들이면 풀 수는 있을 것 같은 문제였는데 백트래킹을 두번이나 써야해서 경우의 수의 경우의 수를 구하다 보니 디버깅이 매우! 매우!! 매우!!!! 힘들었다. 스터디원들도 이 부분에서 굉장히 고생을 했다고 한다 ㅎㅎ.. 코드를 내가 짜고 있는데 내가 어디까지 하고 있는지 모르는 아주 짜증나는 문제였다. 결국 몇 번 시행착오를 거치고 풀어내는데 성공했다! 

 

✏️ 풀이

import java.io.*;
import java.util.*;

public class BOJ16985 {
    static int[][][] maze = new int[5][5][5], mazeCopy = new int[5][5][5];
    static int arr[] = new int[5], floor[] = new int[5];
    static boolean check[] = new boolean[5];
    static int result = Integer.MAX_VALUE;
    static int[][][] count;
    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 l = 0; l < 5; l++) {
                    maze[i][j][l] = Integer.parseInt(st.nextToken());
                }
            }
        }

        floorCheck(0);
        System.out.println((result == Integer.MAX_VALUE) ? -1 : result);

    }
    // 층의 순서를 정하는 백트래킹 메소드
    static void floorCheck(int k) {
        if(k == 5){
            backTracking(0);
            return;
        }

        for(int i = 0; i < 5; i++) {
            if(!check[i]) {
                check[i] = true;
                floor[k] = i;
                floorCheck(k + 1);
                check[i] = false;
            }
        }
    }
    // 회전 방향 정하는 함수
    static void backTracking(int k) {
        if(k == 5) {
            for(int i = 0; i < 5; i++) {
                rotation();
            }

            if(mazeCopy[0][0][0] == 1 && mazeCopy[4][4][4] == 1) {
                bfs();

                if(count[4][4][4] != 0) {
                    result = Math.min(result, count[4][4][4]);
                    if(result == 12) { // 최단거리 출력
                        System.out.println(12);
                        System.exit(0);
                    }
                }

            }
            return;
        }

        for(int i = 1; i < 5; i++) {
            arr[k] = i;
            backTracking(k + 1);
        }
    }
    static void rotation() {
        // 회전함수
        for(int i = 0; i < 5; i++) {
            int idx = floor[i];
            int rotationNum = arr[i];
            for(int j = 0; j < 5; j++) {
                for(int l = 0; l < 5; l++) {
                    if(rotationNum == 1) {
                        mazeCopy[idx][j][l] = maze[i][j][l];
                    }
                    if(rotationNum == 2) {
                        mazeCopy[idx][l][4 - j] = maze[i][j][l];
                    }
                    if(rotationNum == 3) {
                        mazeCopy[idx][4 - j][4 - l] = maze[i][j][l];
                    }
                    if(rotationNum == 4) {
                        mazeCopy[idx][4 - l][j] = maze[i][j][l];
                    }
                }
            }
        }

    }
    static void bfs() {
        // 길찾기 함수
        int[][] dist = {{-1, 0, 0}, {1, 0, 0}, {0, 0, -1}, {0, 0, 1}, {0, 1, 0}, {0, -1, 0}};
        Queue<Pair> queue = new LinkedList<>();
        boolean[][][] visit = new boolean[5][5][5];
        count = new int[5][5][5];
        visit[0][0][0] = true;
        queue.add(new Pair(0, 0, 0));
        while (!queue.isEmpty()) {
            Pair cur = queue.poll();
            for(int i = 0; i < 6; i++) {
                int nz = cur.z + dist[i][0];
                int nx = cur.x + dist[i][1];
                int ny = cur.y + dist[i][2];
                if(nz < 0 || nz >= 5 || nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
                if(visit[nz][nx][ny] || mazeCopy[nz][nx][ny] != 1) continue;
                count[nz][nx][ny] = count[cur.z][cur.x][cur.y] + 1;
                if(nz == 4 && nx == 4 && ny == 4) {
                    return;
                }
                visit[nz][nx][ny] = true;
                queue.add(new Pair(nz, nx, ny));
            }
        }

    }
    public static class Pair {
        int x;
        int y;
        int z;

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

 

풀고 나서 구글링을 통해 다른 사람들 코드도 봤는데 다들 비슷하게 푸신 것 같아서 다행이였다. 처음에 백트래킹을 두번 쓰면서 경우의 수의 경우의 수를 확인면 시간초과나지 않을까.. 라는 생각에 맞는 풀이인가 헷갈렸는데 잘 푼 것 같다!

 

 

솔직히 여태 시뮬레이션 문제 중에 제일 짜증나는 문제였다. 시뮬레이션 문제들 다 재밌다고 느껴졌는데 처음으로 재미없다고 느낌.. 일단 문제를 풀면서 디버깅이 너무 힘들다는게 피로감이 장난 아니였다 ㅎㅎ.. 재밌는 문제만 풀고싶어랑🥲