[BFS, 순열] 16985번 Maaaaaaaaaze 자바(java) 풀이

BOJ 16985번 Maaaaaaaaaze 문제 자바(java) 풀이

• 난이도: 골드3
• BOJ 16985번 Maaaaaaaaaze
  

문제정리

1. 3차원 미로 탈출 대회 개최
2. 5x5 크기의 판이 5개 주어진다.
3. 하얀색 칸은 참가자가 들어갈 수 있는 칸, 검은 칸은 못들어가는 칸이다.
4. 참가자는 주어진 판들을 시계 or 반시계 방향으로 자유롭게 회전할 수 있다. 뒤집을 수는 없다.
5. 회전을 완료한 후 참가자는 판 5개를 쌓는다. 쌓는 순서는 참가자 마음대로 한다.
6. 입구는 참가자가 임의로 선택한 꼭지점. 출구는 입구와 면을 공유하지 않는 꼭짓점
7. 참가자 중에서 본인이 설계한 미로를 가장 적은 이동 횟수로 탈출한 사람이 승리한다.
8. 입구에서 출구로 도달할 수 있는 방법이 없는 경우 탈출이 불가능 하다.
   
   
   

문제 풀이

이 문제는 정말 고려해야할 점이 많습니다. 그리고 문제를 잘 읽어야 합니다.
처음에 판을 임의 순서로 쌓는것을 정리해 놓고도 그걸 적용안해서 헤맸네요 ㅠㅠㅠ

1. 쌓는 순서는 우리 맘이기 때문에 순열을 고려해주어야 합니다.
   기본적인 순열의 형태로 순서를 생각합니다. 순서는 order 배열에
   담습니다.
   만약 배열이 [0,1,4,3,2]가 된다면 0번째 판을 첫번째 그대로 두고 1번째 판을 두번째, 4번째 판을 3번째에, 3번째 판을 4번째에 2번째 판을 5번째에 둡니다.
2. 모든 회전을 고려해야 합니다.
   저는 정말 간단하게 5중 for문을 이용하여 회전하는 모든 경우의 수를 따져주었습니다.
   rotate(i) 함수는 i번째 판을 시계방향으로 90도 만큼 회전시키는 함수입니다.
3. bfs를 통해 탐색합니다.
   일반적인 bfs 함수와 똑같이 작성하면 됩니다.
   만약에 0,0,0과 4,4,4가 1이 아니라면 애초에 시작과 도착을 할 수 없으므로 이 경우는 그냥 넘어갑니다.
   (4,4,4)에 도착하였다면 min 값을 update 해줍니다.
   

백준 16985번 자바(java) 코드

- 실행 시간: 1276 ms
- 메모리: 294136 kb

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.StringTokenizer;
	class Pos{
	int x;
	int y;
	int z;
	int cnt;
	Pos(int x, int y, int z, int cnt){
	this.x = x;
	this.y = y;
	this.z = z;
	this.cnt = cnt;
	}
	}
	class Main{
	static boolean[] visited; // 조합을 위한 visited
	static int[][][] miro; // 원본배열
	static int[][][] c_miro; // 복사한 배열, 이로 miro 이동을 함
	static int[] order; // 판을 놓는 순서
	// 위, 아래, 왼쪽 오른쪽, 왼2, 오2
	static int[] xdir = {0,0,0,0,-1,1};
	static int[] ydir = {0,0,-1,1,0,0};
	static int[] zdir = {-1,1,0,0,0,0};
	static int min;
	public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = null;
	miro = new int[5][5][5];
	c_miro = new int[5][5][5];
	order = new int[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++){
	miro[k][i][j] = Integer.parseInt(st.nextToken());
	}
	}
	}
	min = Integer.MAX_VALUE;
	// 판을 놓는 조합 찾기
	visited = new boolean[5];
	perm(0);
	if(min != Integer.MAX_VALUE)
	System.out.println(min);
	else
	System.out.println(-1);
	}
	private static void perm(int r){
	if(r==5){
	// 순서에 따른 미로 만들기
	for(int i=0; i<5; i++)
	System.arraycopy(miro[order[i]], 0, c_miro[i], 0, c_miro[i].length);
	// 탐색
	// 회전시킬 수 있는 모든 경우를 따짐
	for(int i=0; i<4; i++){
	rotate(4);
	for(int j=0; j<4; j++){
	rotate(3);
	for(int k=0; k<4; k++){
	rotate(2);
	for(int d=0; d<4; d++){
	rotate(1);
	for(int f=0; f<4; f++){
	rotate(0);
	// 출발지와 도착지가 1인 경우에만 bfs 실행
	if(c_miro[0][0][0] == 1 && c_miro[4][4][4] == 1)
	bfs(0,0,0);
	}
	}
	}
	}
	}
	}
	for(int i=0; i<5; i++){
	if(!visited[i]){
	visited[i] = true;
	order[i] = r;
	perm(r+1);
	order[i] = -1;
	visited[i] = false;
	}
	}
	}
	private static void bfs(int a, int b, int c){
	Queue<Pos> q = new LinkedList<>();
	boolean[][][] visited = new boolean[5][5][5];
	q.offer(new Pos(a,b,c,0));
	visited[0][0][0] = true;
	while(!q.isEmpty()){
	Pos p = q.poll();
	int x = p.x;
	int y = p.y;
	int z = p.z;
	int cnt = p.cnt;
	// 도착지에 도착
	if(z == 4 && x == 4 && y == 4){
	min = min > cnt ? cnt : min;
	continue;
	}
	// 모든 방향으로 이동
	for(int j=0; j<6; j++){
	int dx = x + xdir[j];
	int dy = y + ydir[j];
	int dz = z + zdir[j];
	// 유효한 범위이며 방문하지 않았고 c_miro의 값이 0이 아닌경우에만 이동 가능
	if(isValidPosition(dx, dy, dz) && !visited[dz][dx][dy] && c_miro[dz][dx][dy] != 0){
	visited[dz][dx][dy] = true;
	q.offer(new Pos(dx, dy, dz, cnt+1));
	}
	}
	}
	}
	private static boolean isValidPosition(int x, int y, int z){
	if(x < 0 || y < 0 || z < 0 || x >= 5 || y >= 5 || z >= 5) return false;
	return true;
	}
	// 시계 방향 90도 회전
	private static void rotate(int layer){
	int[][] temp = new int[5][5];
	for(int i=0; i<5; i++){
	for(int j=0; j<5; j++){
	temp[i][j] = c_miro[layer][4-j][i];
	}
	}
	System.arraycopy(temp, 0, c_miro[layer], 0, temp.length);
	}
	}

view raw BOJ16985.java hosted with ❤ by GitHub