[백준] 16985. Maaaaaaaaaze (자바 JAVA)

[ 문제 ]  [백준] 16985. Maaaaaaaaaze (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/16985

16985번: Maaaaaaaaaze

---

# 접근 방법 및 풀이 

 

• 주의할 점도 많고 생각보다 까다로웠던 문제. 문제가 불친절하다고 생각한다.
• 먼저, 문제를 제대로 이해하지 못해서 고민을 많이 했는데 이동할 수 있는 경우가 애매하게 표현된 것 같다.
• 보통 2차원 맵 기준, "인접한 칸" 이라고 한다면 현재위치에서 동서남북, 상하좌우, 대각선 포함여부 등이 있는데 여기선 모호하게 "현재 위치한 칸에서 면으로 인접한 칸"인 경우 이동할 수 있다고 되어있다.
• 무슨말이지? 헷갈렸는데, 예제 1번을 보고 이해를 할 수 있었다. 먼저 map은 3차원 배열이기 때문에 5X5크기의 판이 5개가 쌓여있는 형태다. -> map[몇번째 판][행][열] 
• 여기서 이동할 수 있는 경우는 현재 판의 현재 위치에서 위 아래 판, 그리고 현재판의 위치에서 상하좌우를 살펴볼 수 있다.
• 현재 위치가 map[2][r][c]라고 한다면, 이동할 수 있는 경우는 다음과 같다.
• 윗판 map[1][r][c], 아랫판 map[3][r][c], 상 map[2][r-1][c], 하 map[2][r+1][c], 좌 map[2][r][c-1], 우 map[2][r][c+1]
• 이렇게 6가지 방향을 살펴볼 수 있고, 문제에 주어진 대로 1일경우만 이동할 수 있다.
• 이 부분을 이해하고 난 뒤에는 다음과 같이 설계했다.
• 1. 5개의 판 중에 쌓을 순서를 정한다. (순열)
• 2. 판의 회전 방향을 정한다. (중복순열)
• 3. 순서를 정한대로 판을 쌓고, 회전방향까지 정한대로 copy로 map을 copy한다.
• 4. 입구와 출구가 1일 경우, bfs를 통해 입구부터 출구까지의 최단거리를 구한다. (bfs)
• 또한, 구현문제라 설계하고 시간 복잡도를 생각해보아야한다.
• 1번은 5개판 중에 순서를 정하는 것이므로 순열이고 5!이다.
• 2번은 5개의 판의 회전방향을 정해야하는데, 시계든 반시계든 90도씩 회전하는 경우는 4가지고 5개 판이 각각 4개의 방향을 선택할 수 있으므로 4x4x4x4x4 = 4^5이다.
• 5! x 4^5 여기에 bfs까지 고려하면, 2초라는 시간복잡도 안에 가능하다. 여기서 회전방향을 5중 for문으로 구현해도 되지만 그냥 중복순열로 구현했다.
• 근데 구현할 때 회전에서 애를 좀 먹었다. 회전시 0 - 현재상태, 1 - 90도회전, 2 - 180도회전, 3 - 270도 회전으로 생각하고 풀었다. 360도는 어차피 현재상태로 돌아오기 때문이다.
• 잘 풀었는데 답이 안 나 오길래 이상하다고 생각했는데, 판 쌓을 순서를 뽑기만하고 copy에 반영을 하지 않았다.. 하 역시 구현은 정확하게 푸는것이 중요하다.
• 그리고 최단길이가 12가 나올 경우, main함수를 종료시키면 속도가 빨라진다. 예제 1번을 제대로 이해했다면 이 문제에서 최단길이는 제일 작은 값이 12보다 작을 수가 없다. 
• 자세한건 코드참조

 

 

# 주의할 점 

• 판 쌓을 순서만 뽑기만 하진 않았는지, 뽑은 순서대로 반영했는지 체크
• 회전이 잘 되었는지 체크
• 배열 copy를 제대로 하였는지 체크
• 입구와 출구가 1일 경우만 bfs를 돌려야한다.

 

JAVA 코드

package Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class bj16985_Maaaaaaaaaze {

	static int map[][][], copy[][][], ans = Integer.MAX_VALUE;
	static int dir[], order[];
	static boolean check[], visit[][][];
	static int dr[] = { -1, 1, 0, 0, 0, 0 };
	static int dc[] = { 0, 0, -1, 1, 0, 0 };
	static int dz[] = { 0, 0, 0, 0, -1, 1 };

	static class Node {
		int r, c, z, cnt;

		public Node(int r, int c, int z, int cnt) {
			this.r = r;
			this.c = c;
			this.z = z;
			this.cnt = cnt;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		map = new int[5][5][5];
		dir = new int[5];
		order = new int[5];
		check = new boolean[5];
		for (int z = 0; z < 5; z++) {
			for (int r = 0; r < 5; r++) {
				StringTokenizer st = new StringTokenizer(in.readLine());
				for (int c = 0; c < 5; c++) {
					map[z][r][c] = Integer.parseInt(st.nextToken());
				}
			}
		}
		perm(0);
		System.out.println((ans == Integer.MAX_VALUE) ? -1 : ans);
	}

	// 판 쌓는 순서 정하기 - 순열
	private static void perm(int idx) {
		if (idx == 5) {
			copy = new int[5][5][5];
			for (int i = 0; i < order.length; i++) {
				rotation(0);
			}
			return;
		}
		for (int i = 0; i < 5; i++) {
			if (!check[i]) {
				check[i] = true;
				order[idx] = i;
				perm(idx + 1);
				check[i] = false;
			}
		}
	}

	// 4방향 중 회전 - 중복순열
	private static void rotation(int idx) {
		if (idx == 5) {
			for (int i = 0; i < order.length; i++) {
				int pan = order[i];
				int d = dir[pan];
				for (int r = 0; r < 5; r++) {
					for (int c = 0; c < 5; c++) {
						if (d == 0) {
							copy[i][r][c] = map[pan][r][c];
						}
						if (d == 1) {
							copy[i][c][4 - r] = map[pan][r][c];
						}
						if (d == 2) {
							copy[i][4 - r][4 - c] = map[pan][r][c];
						}
						if (d == 3) {
							copy[i][4 - c][r] = map[pan][r][c];
						}
					}
				}
			}
			if (copy[0][0][0] == 1 && copy[4][4][4] == 1)
				bfs();
			return;
		}
		for (int d = 0; d < 4; d++) {
			dir[idx] = d;
			rotation(idx + 1);
		}
	}

	// 최단길이
	private static void bfs() {
		Queue<Node> queue = new LinkedList<Node>();
		visit = new boolean[5][5][5];
		queue.add(new Node(0, 0, 0, 0));
		visit[0][0][0] = true;
		while (!queue.isEmpty()) {
			Node node = queue.poll();
			if (node.r == 4 && node.c == 4 && node.z == 4) {
				ans = Math.min(ans, node.cnt);
				if (ans == 12) {
					System.out.println(12);
					System.exit(0);
				}
				break;
			}
			for (int d = 0; d < 6; d++) {
				int nr = node.r + dr[d];
				int nc = node.c + dc[d];
				int nz = node.z + dz[d];
				if (nr < 0 || nc < 0 || nz < 0 || nr >= 5 || nc >= 5 || nz >= 5 || visit[nz][nr][nc]
						|| copy[nz][nr][nc] == 0)
					continue;
				visit[nz][nr][nc] = true;
				queue.add(new Node(nr, nc, nz, node.cnt + 1));
			}
		}
	}

}

 

 

REVIEW

하.. 이거 1시간 안에 푸는게 목적인데 초과했다ㅠㅠ