[BOJ] 백준 16985 Maaaaaaaaaze (JAVA)

순열, 중복순열

📑 문제

백준 16985번 Maaaaaaaaaze

---

🌱 아이디어

순열과 중복순열을 3차원 배열을 컨트롤해 보자!

 

문제를 접하고 나서, 3차원 배열의 미로 찾기는 이미 몇 번 해보았기 때문에 어렵지 않았다.

가장 고민했던 점은 어떻게 최적의 3차원 미로를 만드냐였다...

 

그래서 순열과 중복순열로 배열을 컨트롤할 수 있는 파라미터를 만드려고 했다

 

중복순열은 배열 한 층을 90도, 180도,  270도를 핸들링할 때 사용했고

당연하게도 인덱스가 겹치면 안 되기 때문에 순열은 3차원 배열의 층을 조립할 때 사용했다

 

순열, 중복순열을 구하고 배열을 핸들링해도 시간초과가 나지 않는다고 확신하고 구현했다.

 

먼저 중복 순열, 순열 구하고

2중 for문으로 각각의 각도에서 배열의 층을 쌓는 방식으로 모든 3차원 배열의 경우의 수를 체크했다.

만든 큐브마다 BFS로 미로 찾기를 진행하고 최단거리를 출력하면 된다!!

---

🌱 코드 및 풀이

	import java.io.*;
	import java.util.*;
	public class Main {
	public static int cnt = 1;
	public static int[][][] arr1;
	public static boolean[][][] vi;
	private static boolean[] visit;
	public static List<Integer> nPr = new ArrayList<>();
	public static List<Integer> nR = new ArrayList<>();
	public static class node {
	int z, x, y, cnt;
	public node(int z, int x, int y, int cnt) {
	this.z = z;
	this.x = x;
	this.y = y;
	this.cnt = cnt;
	}
	}
	// 순열 구하기
	public static void dfs1(int input, int cnt) {
	if (cnt== 5) {
	nPr.add(input);
	return;
	}
	for (int i = 1; i <= 4; i++) {
	dfs1(input*10+i, cnt+1);
	}
	}
	// 중복 순열 구하기
	public static void dfs2(int input, int cnt) {
	if (cnt == 5) {
	nR.add(input);
	return;
	}
	for (int i = 1; i <= 5; i++) {
	if (!visit[i]) {
	visit[i] = true;
	dfs2(input * 10 + i, cnt + 1);
	visit[i] = false;
	}
	}
	}
	// 배열 층 조합하기
	public static int[][][] controlStack(String dir, int[][][] copy) {
	int[][][] tmp = new int[5][5][5];
	for (int i = 0; i < 5; i++) {
	int toIdx = Character.getNumericValue(dir.charAt(i));
	for (int j = 0; j < 5; j++) {
	for (int k = 0; k < 5; k++) {
	tmp[toIdx-1][j][k] = copy[i][j][k];
	}
	}
	}
	return tmp;
	}
	// 배열 층의 각도 조절하기
	public static int[][][] controlCube(String dir) {
	int[][][] tmp = new int[5][5][5];
	// 0은 제자리, 1은 90, 2은 180, 3은 270
	for (int i = 0; i < 5; i++) {
	char control = dir.charAt(i);
	if (control == '1') { // 원위치
	for (int j = 0; j < 5; j++) {
	for (int k = 0; k < 5; k++) {
	tmp[i][j][k] = arr1[i][j][k];
	}
	}
	}
	if (control == '2') { // 90도 회전
	for (int j = 0; j < 5; j++) {
	for (int k = 0; k < 5; k++) {
	tmp[i][k][4 - j] = arr1[i][j][k];
	}
	}
	}
	if (control == '3') { // 180도 회전
	for (int j = 0; j < 5; j++) {
	for (int k = 0; k < 5; k++) {
	tmp[i][4 - j][4 - k] = arr1[i][j][k];
	}
	}
	}
	if (control == '4') { // 270도 회전
	for (int j = 0; j < 5; j++) {
	for (int k = 0; k < 5; k++) {
	tmp[i][4 - k][j] = arr1[i][j][k];
	}
	}
	}
	}
	return tmp;
	}
	// 3차원 배열 미로찾기 BFS
	public static int bfs(int[][][] now) {
	Queue<node> qu = new LinkedList<>();
	int[] dx = {0, 0, -1, 1, 0, 0};
	int[] dy = {-1, 1, 0, 0, 0, 0};
	int[] dz = {0, 0, 0, 0, -1, 1};
	qu.offer(new node(0, 0, 0, 0));
	if (now[0][0][0] == 0 || now[4][4][4] == 0) {
	return -1;
	}
	while (!qu.isEmpty()) {
	node nd = qu.poll();
	if (nd.z == 4 && nd.y == 4 && nd.x == 4) {
	return nd.cnt;
	}
	for (int i = 0; i < 6; i++) {
	int nz = nd.z + dz[i];
	int nx = nd.x + dx[i];
	int ny = nd.y + dy[i];
	if (nz < 0 || nx < 0 || ny < 0 || nz >= 5 || nx >= 5 || ny >= 5) continue;
	if (!vi[nz][ny][nx] && now[nz][ny][nx] == 1) {
	vi[nz][ny][nx] = true;
	qu.offer(new node(nz, nx, ny, nd.cnt + 1));
	}
	}
	}
	return -1;
	}
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st;
	arr1 = new int[5][5][5];
	visit = new boolean[6];
	for (int i = 0; i < 5; i++) {
	for (int j = 0; j < 5; j++) {
	st = new StringTokenizer(br.readLine());
	for (int k = 0; k < 5; k++) {
	arr1[i][j][k] = Integer.parseInt(st.nextToken());
	}
	}
	}
	dfs1(0, 0);
	dfs2(0, 0);
	int answer = Integer.MAX_VALUE;
	for (int dir1 : nPr) {
	vi = new boolean[5][5][5];
	int[][][] cube = controlCube(String.valueOf(dir1));
	for (int dir2 : nR) {
	vi = new boolean[5][5][5];
	int[][][] cubeStack = controlStack(String.valueOf(dir2), cube);
	int res = bfs(cubeStack);
	if (res == -1) continue;
	answer = Math.min(answer, res);
	}
	}
	System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
	}
	}

view raw Maaaaaaaaaze.java hosted with ❤ by GitHub

 

---

🌱 느낀 점

SSAFY에 입과하고 A형 시험을 준비하면서 순열, 조합 문제가 중요하다는 이야기를 듣고 풀어본 문제이다.

생각보다 잘 풀려서 놀랐고, 순열, 중복순열, 조합을 자유롭게 구현할 수 있어서 편하게 풀었다.

 

기발한 문제라서 다른 동기들에게도 추천해 줘야겠다!