[백준] 16985번 : Maaaaaaaaaze

16985번: Maaaaaaaaaze

---

[BFS]

문제의 난이도는 그렇게 높진 않으나 접근하기가 까다로웠다. 각 층은 4방향을 가질 수 있고, 1~5층에 어떤 것을 넣든지 사용자의 결정이다. 사실상 브루트포스로 풀었다.

 

먼저 입력을 받을 때 원 방향, 90도, 180도, -90도 회전시킨 판의 모양을 저장한다.

        for(int i=1; i<6; i++)
            for(int j=1; j<6; j++){
                StringTokenizer st = new StringTokenizer(br.readLine());

                for(int z=1; z<6; z++) {
                    int val = Integer.parseInt(st.nextToken());

                    map[0][i][j][z] = val;
                    map[1][i][6-z][j] = val;
                    map[2][i][6-j][6-z] = val;
                    map[3][i][z][6-j] = val;
                }
            }
            //0 : 원방향
            //1 : 90도 회전
            //2 : 180도 회전
            //3 : -90도 회전

다음은...10중 for문이 등장한다. 애석하게도 나는 이 방법밖에 떠오르지 않았다. 큐브 한 층마다 석판을 갖는다고 할 때,

1층에 올 수 있는 석판은 5개, 이 때 갖을 수 있는 방향은 4개

2층에 올 수 있는 석판은 4개, 이 때 갖을 수 있는 방향은 4개

3층에 올 수 있는 석판은 3개, 이 때 갖을 수 있는 방향은 4개

4층에 올 수 있는 석판은 2개, 이 때 갖을 수 있는 방향은 4개

5층에 올 수 있는 석판은 1개, 이 때 갖을 수 있는 방향은 4개

 

예를 들어 1층에 석판 1이 사용되었고, 2층에 석판 2가 사용되었을 때, 3층에는 석판 1, 2를 제외한 3, 4, 5가 와야한다. 이는 if()에서 조건처리를 해서 중복을 제거하였다.

 

추가적으로 1층의 시작점(1, 1)이 '0'이면 Skip하고,

5층에 도착점(5, 5)가 '0'이면 Skip한다.

 

아래 코드를 차근차근 따라가며 이해해보도록 하자. mat[ ][ ][ ]에 각 배열을 꽂아서 하나의 큐브(Cube)를 생성했다.

        for(int first=1; first<6; first++) {
            for (int a = 0; a < 4; a++) {
            
                if(map[a][first][1][1] == 0) continue;

                for (int second = 1; second < 6; second++) {
                    if (second == first) continue;

                    for (int b = 0; b < 4; b++)
                        for (int third = 1; third < 6; third++) {
                        
                            if (third == first || third == second) continue;

                            for (int c = 0; c < 4; c++)
                                for (int fourth = 1; fourth < 6; fourth++) {
                                
                                    if (fourth == first || fourth == second || fourth == third) continue;

                                    for (int d = 0; d < 4; d++)
                                        for (int fifth = 1; fifth < 6; fifth++) {

                                            if (fifth == first || fifth == second || fifth == third || fifth == fourth) continue;

                                            for (int e = 0; e < 4; e++) {
                                            
                                                if (map[e][fifth][5][5] == 0) continue;

                                                int[][][] mat = new int[6][][];

                                                mat[1] = map[a][first].clone();
                                                mat[2] = map[b][second].clone();
                                                mat[3] = map[c][third].clone();
                                                mat[4] = map[d][fourth].clone();
                                                mat[5] = map[e][fifth].clone();

                                                BFS(mat);
                                            }
                                        }
                                }
                        }
                }
            }
        }

 

BFS에서는 시간을 조금이나마 줄이고자 현재 방문하고 있는 정점까지의 move가 지금 껏 도착점에 도착했을 때의 move (Min)보다 크면 BFS를 종료하도록 설계했다.

# Code </>

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

public class Main {

    static class Point{
        int y, x, z, move;
        public Point(int zz, int yy, int xx, int m){
            z=zz;
            y=yy;
            x=xx;
            move=m;
        }
    }
    static final int INF = 1000000000;
    static int min = INF;
    static int[] Y={-1,1,0,0,0,0}, X={0,0,-1,1,0,0}, Z={0,0,0,0,-1,1};
    static int[][][][] map = new int[4][6][6][6];

    static void BFS(int[][][] mat){

        Queue<Point> Q = new LinkedList<>();
        boolean[][][] visit = new boolean[6][6][6];

        visit[1][1][1] = true;
        Q.add(new Point(1,1,1,0));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int z = p.z;
            int y = p.y;
            int x = p.x;
            int move = p.move;

            if(move > min) break;
            if(z == 5 && y == 5 && x == 5) min = move;

            for(int a=0; a<6; a++){
                int nz = z+Z[a];
                int ny = y+Y[a];
                int nx = x+X[a];

                if(nz < 1 || ny < 1 || nx < 1 || nz > 5 || ny > 5 || nx > 5 || visit[nz][ny][nx] || mat[nz][ny][nx] == 0) continue;

                visit[nz][ny][nx] = true;
                Q.add(new Point(nz, ny, nx, move + 1));
            }
        }
    }

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

        for(int i=1; i<6; i++)
            for(int j=1; j<6; j++){
                StringTokenizer st = new StringTokenizer(br.readLine());

                for(int z=1; z<6; z++) {
                    int val = Integer.parseInt(st.nextToken());

                    map[0][i][j][z] = val;
                    map[1][i][6-z][j] = val;
                    map[2][i][6-j][6-z] = val;
                    map[3][i][z][6-j] = val;
                }
            }

        for(int first=1; first<6; first++) {
            for (int a = 0; a < 4; a++) {
                if(map[a][first][1][1] == 0) continue;

                for (int second = 1; second < 6; second++) {
                    if (second == first) continue;

                    for (int b = 0; b < 4; b++)
                        for (int third = 1; third < 6; third++) {
                            if (third == first || third == second) continue;

                            for (int c = 0; c < 4; c++)
                                for (int fourth = 1; fourth < 6; fourth++) {
                                    if (fourth == first || fourth == second || fourth == third) continue;

                                    for (int d = 0; d < 4; d++)
                                        for (int fifth = 1; fifth < 6; fifth++) {

                                            if (fifth == first || fifth == second || fifth == third || fifth == fourth)
                                                continue;

                                            for (int e = 0; e < 4; e++) {
                                                if (map[e][fifth][5][5] == 0) continue;

                                                int[][][] mat = new int[6][][];

                                                mat[1] = map[a][first].clone();
                                                mat[2] = map[b][second].clone();
                                                mat[3] = map[c][third].clone();
                                                mat[4] = map[d][fourth].clone();
                                                mat[5] = map[e][fifth].clone();

                                                BFS(mat);
                                            }
                                        }
                                }
                        }
                }
            }
        }
        System.out.println(min == INF? -1 : min);
    }
}