[BOJ] 16985번:Maaaaaaaaaze - 완전탐색(Permutation), BFS, 구현

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

16985번: Maaaaaaaaaze

지난번 배열돌리기 문제와 같이, 배열을 회전시키는 등의 구현과 더불어

순열과 BFS 가 모두 활용되는 좋은 문제여서 공부

 

좋은 풀이법 : https://gre-eny.tistory.com/321

 

 

 

 
import java.util.Scanner;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
 
public class Main {
    public static int [][]A;
    public static int [][]B;
    public static int [][]C;
    public static int [][]D;
    public static int [][]E;
    public static int [][][]matrix;
    public static int []dx = {-1,1,0,0,0,0};
    public static int []dy = {0,0,-1,1,0,0};
    public static int []dz = {0,0,0,0,-1,1};
    
    public static int min = Integer.MAX_VALUE;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        A = new int[5][5];
        B = new int[5][5];
        C = new int[5][5];
        D = new int[5][5];
        E = new int[5][5];
        matrix = new int[5][5][5];
 
 
        for(int i=0; i<5; i++){
            for(int j=0; j<5; j++){
                A[i][j] = sc.nextInt();
            } 
        }
        for(int i=0; i<5; i++){
            for(int j=0; j<5; j++){
                B[i][j] = sc.nextInt();
            } 
        }
        for(int i=0; i<5; i++){
            for(int j=0; j<5; j++){
                C[i][j] = sc.nextInt();
            } 
        }
        for(int i=0; i<5; i++){
            for(int j=0; j<5; j++){
                D[i][j] = sc.nextInt();
            } 
        }
        for(int i=0; i<5; i++){
            for(int j=0; j<5; j++){
                E[i][j] = sc.nextInt();
            } 
        }
        int[] arr = new int[5];
        arr[0] = 0; arr[1] = 1;arr[2] = 2; arr[3] = 3;arr[4] = 4;
        
        per1(arr, 0, 5);
        
        if(min==Integer.MAX_VALUE) System.out.println("-1");
        else System.out.println(min);
        sc.close();
    }
 
    static void makeMatrix(int a, int b, int c, int d, int e){
 
        for(int i=0; i<5; i++){
            System.arraycopy(A[i], 0, matrix[a][i], 0, 5);
        }
        for(int i=0; i<5; i++){
            System.arraycopy(B[i], 0, matrix[b][i], 0, 5);
        }
        for(int i=0; i<5; i++){
            System.arraycopy(C[i], 0, matrix[c][i], 0, 5);
        }
        for(int i=0; i<5; i++){
            System.arraycopy(D[i], 0, matrix[d][i], 0, 5);
        }
        for(int i=0; i<5; i++){
            System.arraycopy(E[i], 0, matrix[e][i], 0, 5);
        }
        
 
    }
 
    static void rotate(int d){ //z축:d, 90도회전 
        int[][] tmp = new int[5][5];
        for(int i=0; i<5; i++){
            for(int j=0; j<5; j++){
                tmp[i][j] = matrix[d][4-j][i];
            }
        }
        for(int i=0; i<5; i++){
            System.arraycopy(tmp[i], 0, matrix[d][i], 0, 5);
        }
    }
    static void backtracking(int depth){
        if(depth==5){
            bfs(0,0,0);
            return;
        }
        backtracking(depth+1);
        
        rotate(depth);
        backtracking(depth+1);
 
        rotate(depth);
        backtracking(depth+1);
 
        rotate(depth);
        backtracking(depth+1);
 
        rotate(depth);
 
    }
 
    static void per1(int[] arr, int depth, int n) {
        if(depth == n) {
            makeMatrix(arr[0], arr[1], arr[2], arr[3], arr[4]);
            backtracking(0);
            return;
        }
    
        for(int i=depth; i<n; i++) {
            swap(arr, depth, i);
            per1(arr, depth + 1, n);
            swap(arr, depth, i);
        }
    }
    
    static void swap(int[] arr, int depth, int i) { //두 배열의 값을 바꾸는 Swap 함수 
        int temp = arr[depth];
        arr[depth] = arr[i];
        arr[i] = temp;
    }
 
    static void bfs(int x, int y, int z){
        if(matrix[x][y][z]==0) return ;
        if(x>=5 || y>=5 || z>=5 || x<0 || y<0 || z<0) return ;
 
        Queue<Point> q = new ArrayDeque<>();
 
        boolean[][][] visited = new boolean[5][5][5];
        q.offer(new Point(x,y,z,0));
        visited[x][y][z]=true;
        
        while(!q.isEmpty()){
            Point cur = q.poll();
            if(cur.x==4 && cur.y==4 && cur.z==4){
                min = Math.min(min, cur.len);
                return;
            }
 
            for(int i=0; i<6; i++){
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                int nz = cur.z + dz[i];
 
                if(isValid(nx, ny, nz) && matrix[nx][ny][nz]==1 && !visited[nx][ny][nz]){
                    q.offer(new Point(nx,ny,nz, cur.len+1));
                    visited[nx][ny][nz]=true;
                }
            }
 
        }
    }
    static boolean isValid(int x, int y, int z){
        if(x>=0 && x<5 && y>=0 && y<5 && z>=0 && z<5) return true;
        return false;
    }
 
    static class Point{
        int x,y,z,len;
 
        Point(int x,int y,int z,int len){
            this.x=x;
            this.y=y;
            this.z=z;
            this.len=len;
        }
    }
}