[백준] 16985 Maaaaaaaaaze - 구현(implementation) + 시뮬레이션(Simulation) + Normal Permutation(일반순열) + DFS를 활용한 BruteForce(깊이우선탐색, 브루트포스) + BFS(너비우선탐색) JAVA

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

16985번: Maaaaaaaaaze

코드설명

구현(implementation) + 시뮬레이션(Simulation) + Normal Permutation(일반순열) + DFS(깊이우선탐색) + BFS(너비우선탐색) 을 활용하는 문제입니다.

 

문제로직입니다.

1. getNormalPermutation: 5개의 판에 대한 일반적인 순열을 생성합니다. 각 순열은 판의 배치를 나타냅니다.
2. simulate: 각 순열에 대해 90도씩 회전한 상태를 생성하고 재귀적으로 호출하여 모든 가능한 상태를 탐색합니다.
3. BFS: BFS 알고리즘을 사용하여 시작 지점부터 목적지까지의 최단 경로를 찾습니다.
4. rotateBy90ClockDir: 주어진 2D 배열을 시계 방향으로 90도 회전시키는 함수입니다.
5. Node 클래스: BFS에서 사용되는 노드 클래스로, 현재 레벨, 행, 열, 이동 횟수(cnt)를 저장합니다.

위의 로직대로만 구현하면 되는 구현문제입니다.

블록을 쌓는 순서와 회전하는 경우를 완전탐색하므로, 즉 5! * 4^5 의 연산 개수가 나옵니다.

 

문제에서 놓쳐서 고생했던 점은, 미로의 z Level에서 아래로만 내려간다고 생각했는데, 미로의 위로도 올라갈 수 있습니다.

z LEvel에서 아래쪽으로만 간다고 생각한 이유는 물론 위로도 움직이게 해도 상관없지만, 최대한 빠른 연산을 위해 아래로만 찾아가는 방향이라고 생각했는데 위로도 가서 미로를 탈출할 수 있는경우가 있습니다.

int[] dz = {-1, 1, 0, 0, 0, 0};
int[] dx = {0, 0, -1, 1, 0, 0};
int[] dy = {0, 0, 0, 0, -1, 1};

처음에는 dz = {1, 0, 0, 0, 0}; 으로 했었습니다.

그렇기에, 못가는 예제가 존재했었습니다.

코드

 미로를 쌓을 순서를 먼저 정한뒤 그 정한 값으로 다시 미로들을 각 방향으로 모두 회전시키면서 미로를 쌓습니다.

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 {
	
	public static int N, M, K;
	public static int[] arr;
	public static boolean[][][] map = new boolean[5][5][5]; //false라면
	public static boolean[][][] newMap = new boolean[5][5][5]; //false라면
	public static boolean[][][] visited = new boolean[5][5][5];
	public static boolean[] permVisited = new boolean[5];
	public static int answer = Integer.MAX_VALUE;
	public static int cnt = 1;
	public static int[] dx = {-1,1,0,0, 0, 0};
	public static int[] dy = {0,0,-1,1, 0, 0};
	public static int[] dlevel = {0,0,0,0, 1, -1};
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	for(int t=0;t<5; t++) {
    		
    		for(int i=0; i<5; i++) {
    			StringTokenizer st = new StringTokenizer(br.readLine());
    			for(int j=0; j<5; j++) {
    				map[t][i][j] = Integer.parseInt(st.nextToken()) == 1 ? true : false;
    			}
    		}
    		
    	}
    	
    	getNormalPermutation(0);
    	
    	if(answer == Integer.MAX_VALUE)
    		System.out.println("-1");
    	else
    		System.out.println(answer);
	}
	
	//일반순열을 사용한다. 1 2 3 4 5 가 존재한다면, 1 2 3 5 4 , 1 2 4 3 5  ....
	public static void getNormalPermutation(int level) {
		if(level == 5) {
			simulate(0);
			return ;
		}
		for(int i=0;i<5;i++) {
			if(permVisited[i] == false) {
				
				permVisited[i] = true;
				for(int j=0; j<5; j++) {
					for(int k=0; k<5; k++) {
						newMap[level][j][k] = map[i][j][k]; //i번쨰 판을 level 번쨰 판에 복사해준다.	
					}
				}
				getNormalPermutation(level + 1);
				permVisited[i] = false;
				
			}
			
		}
		
		
	}
	
	public static void simulate(int level) {
		if(level == 5) {
			//이제 MAP을 돌면서 가능한지 확인한다. BFS를 활용해서 최단거리를 찾는것이 방법이다.
			//만약 map[5][4][4] 에 도착한다면 완성일것이다.
			if(newMap[0][0][0] == true)
				BFS();
			
			return ;
		}
		
		
		//원본저장.
		boolean[][] mapCopy = new boolean[5][5];
		//테스트에 사용할 mapTemp;
		boolean[][] mapTemp = new boolean[5][5];
		for(int i=0;i<5;i++) {
			for(int j=0;j<5;j++) {
				mapTemp[i][j] = newMap[level][i][j];
				mapCopy[i][j] = newMap[level][i][j];
			}
		}
		
		for(int dir = 0; dir < 4; dir++) {
			mapTemp = rotateBy90ClockDir(mapTemp);
			for(int i=0;i<5;i++) {
				for(int j=0;j<5;j++) {
					newMap[level][i][j] = mapTemp[i][j];
				}
			}
			simulate(level + 1);
		}
		
		//해당 레벨 원상복구.
		for(int i=0;i<5;i++) {
			for(int j=0;j<5;j++) {
				newMap[level][i][j] = mapCopy[i][j]; 
			}
		}
		
	}
	
	public static void BFS() {
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(0, 0, 0, 0));
		visited = new boolean[5][5][5];
		visited[0][0][0] = true;
		
		while(!q.isEmpty()) {
			Node temp = q.poll();
			
			if(temp.level == 4 && temp.r == 4 && temp.c == 4) {
				answer = Math.min(answer, temp.cnt);
				return ;
			}
			
			for(int dir = 0; dir < 6; dir++) {
				int nr = temp.r + dx[dir];
				int nc = temp.c + dy[dir];
				int nlevel = temp.level + dlevel[dir];
				
				if(nr < 0 || nr >= 5 || nc < 0 || nc >= 5 || nlevel >= 5 || nlevel < 0) continue;
				if(visited[nlevel][nr][nc] == true) continue;
				
				if(newMap[nlevel][nr][nc] == true) {					
					visited[nlevel][nr][nc] = true;
					q.offer(new Node(nlevel, nr, nc, temp.cnt + 1));
				}
			}
			
		}
		
	}
	
	
	//시계방향으로 90도 회전.
	public static boolean[][] rotateBy90ClockDir(boolean[][] map){
		boolean[][] newMaps = new boolean[5][5];
		
		for(int i=0;i<5;i++) {
			for(int j=0;j<5;j++) {
				newMaps[j][5 - i - 1] = map[i][j];
			}
		}
		
		return newMaps;
	}
}
 
 
class Node{
	int level;
	int r;
	int c;
	int cnt;
	public Node(int level, int r, int c, int cnt) {
		this.level = level;
		this.r = r;
		this.c = c;
		this.cnt = cnt;
	}
 
}

미로를 쌓을순서를 정하면서 바로 각 방향으로 회전시켜서 완전탐색 합니다.

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 {
	public static int N, M, D;
	public static int answer = Integer.MAX_VALUE;
	public static int[][][] map = new int[5][5][5];
	public static int[][][] makeMap = new int[5][5][5];
	public static boolean[] usedBlock = new boolean[5];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int z=0; z<5;z++) {
			for(int i=0;i<5;i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for(int j=0;j<5;j++) {
					map[z][i][j] = Integer.parseInt(st.nextToken());
				}
			}
		}
		
		simulate(0);
		if(answer == Integer.MAX_VALUE) {
			answer = -1;
		}
		System.out.println(answer);
		
	}
	public static void simulate(int level) {
		if(level == 5) {
			BFS();
			return ;
		}
		
		//판을 쌓는것부터 먼저 고려합니다.
		for(int kind = 0; kind < 5; kind++) {
			if(usedBlock[kind] == false) {
				usedBlock[kind] = true;
				for(int dir = 0; dir < 4; dir++) {
					makeMap[level] = rotateBy90Degree(map[kind]);
					simulate(level + 1);
				}
				usedBlock[kind] = false;
			}
		}
	
	}
	
	public static int[][] rotateBy90Degree(int[][] tempMap){
		int[][] newMap = new int[5][5];
		
		for(int i=0;i<5;i++) {
			for(int j=0;j<5;j++) {
				newMap[i][j] = tempMap[i][j];
			}
		}
		
		for(int i=0;i<5;i++) {
			for(int j=0;j<5;j++) {
				tempMap[j][4-i] = newMap[i][j];
			}
		}
		
		return tempMap;
	}
	
	public static void BFS() {
		int[] dz = {-1, 1, 0, 0, 0, 0};
		int[] dx = {0, 0, -1, 1, 0, 0};
		int[] dy = {0, 0, 0, 0, -1, 1};
		
		boolean[][][] visited = new boolean[5][5][5];
		Queue<Node> q = new LinkedList<>();
		if(makeMap[0][0][0] == 1){
			q.offer(new Node(0, 0, 0, 0));
			visited[0][0][0] = true;
		}
		
		while(!q.isEmpty()) {
			Node temp = q.poll();
			if(temp.z == 4 && temp.r == 4 && temp.c == 4) {
				answer = Math.min(answer, temp.time);
				return ;
			}
			
			for(int dir=0;dir<6;dir++) {
				int nz = temp.z + dz[dir];
				int nr = temp.r + dx[dir];
				int nc = temp.c + dy[dir];
				
				if(nz < 0 || nz >= 5 || nr < 0 || nr >= 5 || nc < 0 || nc >= 5) continue;
				if(makeMap[nz][nr][nc] == 0) continue;
				if(visited[nz][nr][nc] == true) continue;
				
				visited[nz][nr][nc] = true;
				q.offer(new Node(nz, nr, nc ,temp.time + 1));
			}
		}
	}
}
 
class Node{
	int z;
	int r;
	int c;
	int time = 0;
	public Node(int z, int r, int c, int time) {
		this.z=z;
		this.r=r;
		this.c=c;
		this.time = time;
	}
}