[백준, 1917, 자바] 정육면체 전개도

링크 : https://www.acmicpc.net/problem/1917

1917번: 정육면체 전개도

 

1. 문제 핵심

1. 6 * 6 안에 이어져있는 6개의 1이 존재.
2. 해당 1들로 정육면제를 만들 수 있는지 확인하는 문제

 

---

2. 문제 접근

그림 0. 정육면체를 평면으로 만들었을 때

주사위를 펼치면 이러한 모양이 된다.

그림 1. 정육면체의 각 숫자 기준 상, 하, 좌, 우

각 자리를 기준으로 상, 하, 좌, 우는 위 이미지와 같이 이루어져 있다.

그림 2. 정육면체 가능 케이스

주사위가 가능한지 여부 검사는 다음과 같다.

1. 첫 위치는 무조건 0을 배치한다.
2. 0 이후에 배치될 숫자는 그림 1의 배치대로 놓았을 때 2가 입력될 수 있다.
3. 0-2를 기준으로 했을 때 그림 1에서 0-2와 90도의 각도 차이가 발생한다.
4. 따라서 2를 기준으로 그 다음 숫자를 입력할 때 그림 1의 기준으로 2 위에는 5가 들어가겠지만 90도의 각도 차이를 감안했을 때 1이 입력됨을 알 수 있다.
5. 이러한 방식으로 숫자들을 채워나간다.
6. 만약 숫자들을 채우다가 중복되는 숫자가 입력되면 해당 케이스는 정육면체가 불가능함을 알 수 있다.

 

그림 3. 정육면체 불가능 케이스

 

---

5. 자바 코드

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

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int[][] bd = new int[6][6];

		boolean[][] isVist = new boolean[6][6];

		int[][] dydx = new int[][] { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
		int[][][] eachDiceNum = new int[][][] { //
				{ { -1, 1, -1 }, { 4, 0, 2 }, { -1, 3, -1 } }, //
				{ { -1, 5, -1 }, { 4, 1, 2 }, { -1, 0, -1 } }, //
				{ { -1, 5, -1 }, { 1, 2, 3 }, { -1, 0, -1 } }, //
				{ { -1, 5, -1 }, { 2, 3, 4 }, { -1, 0, -1 } }, //
				{ { -1, 5, -1 }, { 3, 4, 1 }, { -1, 0, -1 } }, //
				{ { -1, 3, -1 }, { 4, 5, 2 }, { -1, 1, -1 } } };

		Queue<int[]> q = new LinkedList<int[]>();
		char a;
		// 다이스 중복 검사
		boolean[] dice = new boolean[6];
		int tmp = 0, dir = 0, cnt = 0, y = 0, x = 0, crntY = 0, crntX = 0, nextY = 0, nextX = 0, pos = 0, nextPos = 0;
		int[] tmpYX;
		boolean isDice = true;
		// 3번 나눠서 진행
		for (int l = 0; l < 3; l++) {
			bd = new int[6][6];
			isVist = new boolean[6][6];
			dice = new boolean[6];
			isDice = true;
			// 6행
			for (int i = 0; i < 6; i++) {
				st = new StringTokenizer(br.readLine());
				// 6열
				for (int j = 0; j < 6; j++) {
					bd[i][j] = -1;
					if (st.nextToken().equals("1")) {
						bd[i][j] = 0;
						// 마지막 1 위치 저장
						y = i;
						x = j;
					}
				}
			}

			q.add(new int[] { y, x, 0 });
			dice[0] = true;
			isVist[y][x] = true;
			cnt = 0;
			bd[y][x] = 0;
			while (!q.isEmpty()) {
				tmpYX = q.poll();
				crntY = tmpYX[0];
				crntX = tmpYX[1];
				pos = tmpYX[2];
				cnt++;
				dir = 0;

				// 기준점을 발견하기 위해 사용
				// 2번째 방문 위치부터 사용
				if (cnt != 1) {
					// 4방 탐색하며 이전에 방문한 이력이 있는지 확인
					LOOP: for (int i = 0; i < 4; i++) {
						nextY = crntY + dydx[i][0];
						nextX = crntX + dydx[i][1];

						// 갈 수 없는 경우, 방문하지 않은 경우, 주사위가 놓이지 않은 경우 제외
						if (nextY == -1 || nextY == 6 || nextX == -1 || nextX == 6 || !isVist[nextY][nextX]
								|| bd[nextY][nextX] == -1)
							continue;
						nextPos = bd[nextY][nextX];

						// i 는 방향
						// nextPos는 해당 방향에 저장된 숫자

						for (int j = 0; j < 4; j++) {
							// 사방탐색하며 같은 숫자를 통해 방향성을 발견해야 함
							if (eachDiceNum[pos][1 + dydx[j][0]][1 + dydx[j][1]] == nextPos) {
								// j는 해당 숫자 기준으로 방향성을 탐색
								//
								dir = j - i;

								break LOOP;
							}
						}
					}
				}
				// 상, 주, 하, 좌
				for (int i = 0; i < 4; i++) {
					nextY = crntY + dydx[i][0];
					nextX = crntX + dydx[i][1];

					// 이미 방문했다면 or 방문할 수 없다면
					if (nextY == -1 || nextY == 6 || nextX == -1 || nextX == 6 || isVist[nextY][nextX]
							|| bd[nextY][nextX] == -1)
						continue;

					// 다음 자리에 놓일 수 있는 수를 탐색
					// 상
					tmp = i;
					tmp += dir;
					tmp = (tmp + 4) % 4;
					
					if (tmp == 0) {
						if (pos == 0) {
							nextPos = 1;
						} else if (pos == 1) {
							nextPos = 5;
						} else if (pos == 2) {
							nextPos = 5;
						} else if (pos == 3) {
							nextPos = 5;
						} else if (pos == 4) {
							nextPos = 5;
						} else {
							nextPos = 3;
						}
					}
					// 우
					else if (tmp == 1) {
						if (pos == 0) {
							nextPos = 2;
						} else if (pos == 1) {
							nextPos = 2;
						} else if (pos == 2) {
							nextPos = 3;
						} else if (pos == 3) {
							nextPos = 4;
						} else if (pos == 4) {
							nextPos = 1;
						} else {
							nextPos = 2;
						}
					}
					// 하
					else if (tmp == 2) {
						if (pos == 0) {
							nextPos = 3;
						} else if (pos == 1) {
							nextPos = 0;
						} else if (pos == 2) {
							nextPos = 0;
						} else if (pos == 3) {
							nextPos = 0;
						} else if (pos == 4) {
							nextPos = 0;
						} else {
							nextPos = 1;
						}
					}
					// 좌
					else {
						if (pos == 0) {
							nextPos = 4;
						} else if (pos == 1) {
							nextPos = 4;
						} else if (pos == 2) {
							nextPos = 1;
						} else if (pos == 3) {
							nextPos = 2;
						} else if (pos == 4) {
							nextPos = 3;
						} else {
							nextPos = 4;
						}
					}

					// 중복될 시 중단
					if (dice[nextPos]) {
						isDice = false;
						break;
					}

					dice[nextPos] = true;
					if (!isVist[nextY][nextX]) {
						bd[nextY][nextX] = nextPos;
						isVist[nextY][nextX] = true;
						q.add(new int[] { nextY, nextX, nextPos });
					}

				}
			}
			if (isDice)
				System.out.println("yes");
			else
				System.out.println("no");
		}
	}
}