[BOJ] 백준 16985 Maaaaaaaaaze

[문제]

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

 

 

[소스 코드]

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

public class Main {
	static int result = Integer.MAX_VALUE;
	static int[][][] map;
	static int[] order = new int[5];
	static boolean[] select = new boolean[5];
	static int[] rotate;
	static int[] dir = new int[5];
	static int[] dz = {1,-1,0,0,0,0};
	static int[] dr = {0,0,1,-1,0,0};
	static int[] dc = {0,0,0,0,-1,1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		map = new int[5][5][5];
		for(int k=0;k<5;k++) {
			for(int i=0;i<5;i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0;j<5;j++) {
					map[k][i][j] = Integer.parseInt(st.nextToken());
				}
			}
		}
		perm(0);
		System.out.println((result==Integer.MAX_VALUE)? -1 : result);
	}
	private static void perm(int idx) {
		if(idx==5) {
			rotate(0);
			return;
		}
		for(int i=0;i<5;i++) {
			if(!select[i]) {
				select[i] = true;
				order[idx] = i;
				perm(idx+1);
				select[i] = false;
			}
		}
	}
	private static void rotate(int idx) {
		if(idx==5) {
			int[][][] copyM = new int[5][5][5];
			for(int k=0;k<5;k++) {
				int pan = order[k];
				int d = dir[k];
				for(int i=0;i<5;i++) {
					for(int j=0;j<5;j++) {
						if(d==0) {
							copyM[k][i][j] = map[pan][i][j];
						}
						if(d==1) {
							copyM[k][j][4-i] = map[pan][i][j];
						}
						if(d==2) {
							copyM[k][4-i][4-j] = map[pan][i][j];
						}
						if(d==3) {
							copyM[k][4-j][i] = map[pan][i][j];
						}
					}
				}
			}
			if(copyM[0][0][0]==1 && copyM[4][4][4]==1) 
				bfs(copyM);
			return;
		}
		for(int d=0;d<4;d++) {
			dir[idx] = d;
			rotate(idx+1);
		}
	}
	private static void bfs(int[][][] copyM) {
		Queue<int[]> q = new LinkedList<>();
		boolean[][][] visit = new boolean[5][5][5];
		visit[0][0][0] = true;
		q.offer(new int[] {0,0,0,0});  
		
		while(!q.isEmpty()) {
			int[] curr = q.poll();
			if(curr[0]==4 && curr[1]==4 && curr[2]==4) {
				result = Math.min(result, curr[3]);
				return;
			}
			for(int d=0;d<6;d++) {
				int nz = curr[0] + dz[d];
				int nr = curr[1] + dr[d];
				int nc = curr[2] + dc[d];
				if(nz<0 || nz>=5 || nr<0 || nr>=5 || nc<0 || nc>=5 || visit[nz][nr][nc] || copyM[nz][nr][nc]==0) continue;
				visit[nz][nr][nc] = true;
				q.offer(new int[] {nz,nr,nc,curr[3]+1});
			}
		}
	}
}