/ BOJ

BOJ_2116_주사위쌓기_JAVA

문제 : 주사위쌓기

링크 : BOJ_2116_주사위쌓기

접근 방식

규칙 깔리는 주사위의 윗면과 놓는 주사위의 밑면의 숫자가 같아야한다.

ABCDEF 순으로 값이 주어진다.

순서는 1번 주사위부터 N번주사위까지 주어짐

A-F, B-D, C-E가 윗면, 아랫면이 될 수 있다. 이 세가지 경우를 조사해

경우의 수 별로 나머지 주사위들의 최댓값을 모아 출력하면 될 것 같았다. 하지만 모든 경우의 수를 따지려면, 주사위 개수만큼 for문을 중첩해야 할 것 같았다. 따라서 재귀를 이용해서 풀어보기로 했다.

주사위를 숫자로 매칭했을 때 다음과 같다. 1-A, 2-B, 3-C, 4-D, 5-E, 6-F

그리고, 어느 한 쪽을 주사위의 밑면으로 한다면 그 반대편 의 index는 다음과 같다. 1-6, 2-4, 3-5

1번에서 먼저 1번 주사위를 선택한다. 그 다음부터는 주사위를 쌓는 방향을 바꿀수 없다. 첫 주사위의 방향대로 나머지 주사위의 옆면의 수가 정해진다.

이게 DFS가 맞는지는 모르겠지만 1번주사위부터 6번주사위까지 경우의 수를 한 번씩 모두 구하는 것이라고 생각해서 DFS라고 이름지었다.

함수의 실행은 대략 이렇게 이루어진다.

먼저 주사위를 놓으면 반대편 주사위까지는 사용을 못한다.

나머지 주사위 값 중에서 최댓값을 구해 더하고, 다음 주사위로 넘어간다. 반대편 주사위의 값을 다음 재귀로 넘겨준다.

풀이 방법

  1. 주사위 개수를 읽어와 변수에 저장한다. 주사위 정보는 2차원 배열을 생성하여 저장한다.

  2. i를 1부터 6까지 반복한다. 여기서 1~6은 첫 번째 주사위의 바닥에 두는 수를 뜻한다. 반복할 때마다 dfs 메서드를 호출한다.

  3. dfs 메서드는 인자값으로 int 타입과 1차원 배열을 받는다. int 타입에는 바닥에 놓을 1번주사위의 값이, 배열에는 1번 주사위의 정보가 주어진다.

  4. 먼저 6의 크기의 1차원 boolean 배열을 선언한다. 그 후, 인자값으로 받아온 주사위 정보를 탐색하여 해당 밸류를 가지고 있는 index를 찾아 저장한다.

  5. 규칙(1-6, 2-4, 3-5)대로, 밑면과 밑면의 대응되는 윗면을 visited 배열에서 방문처리한다. 해당 규칙은 따로 메서드(search 메서드)로 꺼내두었다.

  6. 1부터 6까지 반복한다. 만약 해당 위치가 이미 방문한 상태라면 continue하고, 아닐 경우 주사위의 나머지 값 중에서 최댓값을 구해 저장한다.

  7. 해당 최댓값을 누적시키고 재귀호출한다. 재귀호출하는 인자값으로는 현재 놓여진 주사위의 윗면의 index, 그리고 다음 주사위의 배열을 인자값으로 넘겨준다.

  8. 기저조건으로는 cnt가 N-1이 되었을 때, 즉 N번 주사위까지 탐색이 되었을 때 재귀가 종료된다.

  9. 1번 dfs를 돌릴 때마다 1면을 바닥으로 했을 때의 최댓값이 나타난다. 즉, 6번 dfs를 돌리면서 최댓값을 저장하면 주사위 N개를 쌓아올릴때의 옆면의 최댓값을 구할 수 있다.

  10. 구한 최댓값을 출력한다.

소스 코드


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

public class BOJ_2116_주사위쌓기 {


	/* 규칙 깔리는 주사위의 윗면과 놓는 주사위의 밑면의 숫자가 같아야한다.
	 * ABCDEF 순으로 값이 주어짐. A는 윗면, F는 아랫면
	 * 순서는 1번 주사위부터 6번주사위까지 주어짐
	 * A-F, B-D, C-E가 윗면, 아랫면이 될 수 있다. 이 세가지 경우를 조사해
	 * 경우의 수 별로 나머지 주사위들의최댓값을 모아 출력하면 되지않을까
	 *  */
	static int max, sum, N;
	static int arr[][];
	static int cnt = 0;
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(in.readLine());
		arr = new int[N][6];
		StringTokenizer st;
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(in.readLine()," ");
			for(int j=0;j<6;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}


		// 1-A, 2-B, 3-C, 4-D, 5-E, 6-F
		// 1-6, 2-4, 3-5
		// 1-6 제외
		// 1번에서 가장 작은 수를 먼저 바닥으로 쓰면 그 반대편의 수는 다음 사람은 못쓴다.
		// 굳이 가장 작은수를 바닥으로 쓸 필요없이 6만 남길 수 있으면 된다.
		// 먼저 1번 주사위를 선택한다.(숫자 자유)그 다음부터는 그냥 바꿀수 없이 정해짐
		// dfs를 해보자
		// 먼저 주사위를 놓으면 반대편 주사위까지는 사용을 못한다.
		// 나머지 주사위 값 중에서 최댓값을 구해 더하고, 다음 주사위로 넘어간다. 반대편 주사위의 값을 다음 재귀로 넘겨준다.
		for(int i=1;i<=6;i++) {
			sum = 0;
			cnt = 0;
			dfs(i,arr[0]);
			max = Math.max(max, sum);
		}
		System.out.println(max);
	}

	public static void dfs(int value,int dice[]) {



		int index = 0;

		boolean[] visited = new boolean[6];

		for(int i=0;i<6;i++) {
			if(dice[i] == value) {
				index = i;
//				System.out.println(i);
			}
		}

		visited[index] = true;
		visited[search(index)] = true;
//		System.out.println(index+":"+search(index)+":"+value+":"+cnt);
		int max = 0;
		for(int i=0;i<6;i++) {
			if(visited[i] == true) {
				continue;
			}
			max = Math.max(max, dice[i]);
		}

//		System.out.println(Arrays.toString(visited));

		sum = sum + max;

		if(cnt == N-1) {
//			System.out.println(sum);
			return;
		}

		dfs(dice[search(index)],arr[++cnt]);

	}


	public static int search(int index) {

		switch(index) {
		case 0:
			return 5;
		case 1:
			return 3;
		case 2:
			return 4;
		case 3:
			return 1;
		case 4:
			return 2;
		case 5:
			return 0;
		}

		return -1;
	}

}