백준 16985 - (Java) Maaaaaaaaaze

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

16985번: Maaaaaaaaaze

유형

구현, 너비우선탐색

 

문제분석

위 순서대로 구현하시면 됩니다.

 

회전

먼저 arraycopy라이브러리를 사용하여, 원본을 복사해줍니다. 그리고 map에 시계방향 회전을 합니다.

 

순열로 판의 위치 재배열

순열에서 중복은 허용하지 않기 때문에, contains라이브러리를 사용했습니다.

list에 {0,1,2,3,4} or {0,1,2,4,3} ... 등으로 총 5!만큼 만들어줍니다.

 

Bfs

2차원 bfs의 포맷과 똑같습니다. 다른점은 동서남북 + 위,아래 까지 추가해서 총 6방향에 대해 탐색해주면 됩니다.

 

코드

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

public class Main {
	static int map[][][], newmap[][][];
	static int arr[][] = { { 0, 0 }, { 0, 4 }, { 4, 0 }, { 4, 4 } };
	static int D[][] = { { -1, 0, 0 }, { 1, 0, 0 }, { 0, -1, 0 }, { 0, 0, 1 }, { 0, 1, 0 }, { 0, 0, -1 } };
	static int INF = 987654321, result = INF;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		map = new int[5][5][5];
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				st = new StringTokenizer(in.readLine());
				for (int k = 0; k < 5; k++) {
					map[i][j][k] = stoi(st.nextToken());
				}
			}
		}
		recur(0);
		if (result == INF) {
			System.out.println(-1);
		} else
			System.out.println(result);
	}
	//회전함수
	static void recur(int dep) {
		if (dep == 5) {
			// 판 쌓기
			upstair(new ArrayList<>());
			return;
		}
		// 회전
		for (int n = 0; n < 4; n++) {
			int[][] copy = new int[5][5];
			for (int i = 0; i < 5; i++) {
				System.arraycopy(map[dep][i], 0, copy[i], 0, 5);
			}

			for (int r = 0; r < 5; r++) {
				for (int c = 0; c < 5; c++) {
					map[dep][c][4 - r] = copy[r][c];// 시계방향 회전
				}
			}
			recur(dep + 1);
		}
	}
	//판의 순서 순열
	static void upstair(List<Integer> list) {
		if (list.size() == 5) {
			newmap = new int[5][5][5];
			// 층을 재배열
			for (int origin = 0; origin < 5; origin++) {
				int newpos = list.get(origin);
				for (int j = 0; j < 5; j++) {
					System.arraycopy(map[origin][j], 0, newmap[newpos][j], 0, 5);
				}
			}
			// 시작, 끝값 구하기
			if (newmap[0][0][0] == 1 && newmap[4][4][4] == 1)
				bfs(new int[] {0,0}, new int[] {4,4});
			return;
		}
		// 재배열할 순서 구하기
		for (int i = 0; i < 5; i++) {
			if (!list.contains(i)) {
				list.add(i);
				upstair(list);
				list.remove(list.size() - 1);
			}
		}
	}

	static void bfs(int start[], int end[]) {
		Queue<int[]> q = new LinkedList<>();
		boolean visit[][][] = new boolean[5][5][5];
		q.add(new int[] { 0, start[0], start[1], 0 });
		visit[0][start[0]][start[1]] = true;
		while (!q.isEmpty()) {
			int cur[] = q.poll();
			if (cur[0] == 4 && cur[1] == end[0] && cur[2] == end[1]) {
				result = Math.min(result, cur[3]);
				return;
			}
			for (int k = 0; k < 6; k++) {
				int nh = cur[0] + D[k][0];
				int nr = cur[1] + D[k][1];
				int nc = cur[2] + D[k][2];
				if (nh < 0 || nh >= 5 || nr < 0 || nr >= 5 || nc < 0 || nc >= 5 || visit[nh][nr][nc]
						|| newmap[nh][nr][nc] == 0)
					continue;
				visit[nh][nr][nc] = true;
				q.add(new int[] { nh, nr, nc, cur[3] + 1 });
			}
		}
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}