[백준/boj] 2116: 주사위 쌓기 (Java) / 브루트포스 / 구현

문제

2116번: 주사위 쌓기

풀이

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

public class Main_BOJ_2116_주사위쌓기 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N;
	static int[][] dices;
	static boolean[] isTop = new boolean[6];
	static int maxNum = 0;

	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(br.readLine());
		dices = new int[N][6];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 6; j++) {
				dices[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		// 0-5 1-3 2-4
		boolean[] visited = new boolean[7];
		for (int i = 0; i < 6; i++) {
			int pair = findPair(i);
			visited[pair] = true;
			if (!visited[i]) {
				doStack(dices[0][i], dices[0][pair], 0, 0);
				doStack(dices[0][pair], dices[0][i], 0, 0);
			}
		}
		System.out.println(maxNum);

	}

	// top, bottom은 인덱스가 아니라 주사위에 적힌 숫자
	private static void doStack(int top, int bottom, int cnt, int total) {
		int sideMax = 0;
		if (cnt == N - 1) {
			for (int i = 0; i < 6; i++) {
				if (dices[cnt][i] != top && dices[cnt][i] != bottom) {
					sideMax = Math.max(sideMax, dices[cnt][i]);
				}
			}
			total += sideMax;
			maxNum = Math.max(total, maxNum);
			return;
		}

		int topIdx = -1;
		for (int i = 0; i < 6; i++) {
			if (dices[cnt][i] != top && dices[cnt][i] != bottom) 
				sideMax = Math.max(sideMax, dices[cnt][i]);

			if (dices[cnt+1][i] == top) topIdx = i;
		}

		// 다음 주사위의 bottom은 이전 주사위의 top이 되어야 한다.(같은 수가 마주봐야 하기 때문)
		doStack(dices[cnt + 1][findPair(topIdx)], top, cnt + 1, total + sideMax);
	}

	// 0-5 1-3 2-4
	private static int findPair(int i) { // top 인덱스가 넘어오면, bottom 인덱스를 반환
		int pair = -1;
		switch (i) {
			case 0: pair = 5; break;
			case 5: pair = 0; break;
		
			case 1: pair = 3; break;
			case 3: pair = 1; break;
			
			case 2: pair = 4; break;
			case 4:	pair = 2; break;
		}
		return pair;
	}
}

먼저 위 사진을 통해 A - F, B - D, C - E 는 서로 윗면일 때 아랫면이 되는 pair임을 알 수 있다. A~F 를 0~5 인덱스로 구분해서 사용할 것이다. 

• dices[][] : N개의 주사위를 받아와 정보를 저장한다. 예를 들어, dices[0][2]는 첫번째 주사위의 C번에 써있는 숫자이다.

---

첫번째 주사위를 쌓으면서 가지를 뻗어나가 모든 경우를 살펴보고, 그 중 최댓값을 출력하도록 전체 코드를 구현했다. 

		// 0-5 1-3 2-4
		boolean[] visited = new boolean[7];
		for (int i = 0; i < 6; i++) {
			int pair = findPair(i);
			visited[pair] = true;
			if (!visited[i]) {
				doStack(dices[0][i], dices[0][pair], 0, 0);
				doStack(dices[0][pair], dices[0][i], 0, 0);
			}
		}
        // doStack(int top, int bottom, int cnt, int total)

먼저 main에서 input을 받은 후 코드를 살펴보자. 위 코드는 첫번째 주사위의 A부터 F까지 모든 숫자가 top인 경우, bottom인 경우로 쌓기를 시작하도록 함수를 호출하는 코드이다.

• for문을 통해 A부터 F까지 살펴본다. 

첫번째 주사위가 위와 같을 때로 살펴보자.

• 내가 A의 pair를 찾고 싶다면 findPair(0)을 호출할 것이다. 그럼 findPair는 5를 반환한다. 이는 A가 넘어왔을 때, F를 반환한것과 같은 의미이다.

	// 0-5 1-3 2-4
	private static int findPair(int i) { // top 인덱스가 넘어오면, bottom 인덱스를 반환
		int pair = -1;
		switch (i) {
			case 0: pair = 5; break;
			case 5: pair = 0; break;
		
			case 1: pair = 3; break;
			case 3: pair = 1; break;
			
			case 2: pair = 4; break;
			case 4:	pair = 2; break;
		}
		return pair;
	}

• main에서는 visited[5] 를 true로 바꿔주어 나중에 top이 4(dices[0][5])인 경우와, bottom이 4인 경우가 중복 호출되지 않도록 방지한다.
• doStack은 dices[0][0] 이 top 인 경우와 dices[0][0]이 bottom인 경우로 총 두번 호출 된다.
  ==> doStack(2, 4, 0, 0) 과 doStack(4, 2, 0, 0)

if (!visited[i]) {
	doStack(dices[0][i], dices[0][pair], 0, 0);
	doStack(dices[0][pair], dices[0][i], 0, 0);
}

---

	// top, bottom은 인덱스가 아니라 주사위에 적힌 숫자
	private static void doStack(int top, int bottom, int cnt, int total) {
		int sideMax = 0;
		if (cnt == N - 1) {
			for (int i = 0; i < 6; i++) {
				if (dices[cnt][i] != top && dices[cnt][i] != bottom) {
					sideMax = Math.max(sideMax, dices[cnt][i]);
				}
			}
			total += sideMax;
			maxNum = Math.max(total, maxNum);
			return;
		}

		int topIdx = -1;
		for (int i = 0; i < 6; i++) {
			if (dices[cnt][i] != top && dices[cnt][i] != bottom) 
				sideMax = Math.max(sideMax, dices[cnt][i]);

			if (dices[cnt+1][i] == top) topIdx = i;
		}

		// 다음 주사위의 bottom은 이전 주사위의 top이 되어야 한다.(같은 수가 마주봐야 하기 때문)
		doStack(dices[cnt + 1][findPair(topIdx)], top, cnt + 1, total + sideMax);
	}

doStack 함수를 살펴보자. (cnt번째 주사위를 쌓는 함수)

• top: 주사위 윗면의 숫자 (다음 주사위의 아랫면 숫자가 된다: 마주봐야 하기 때문)
• bottom: 주사위 아랫면의 숫자
• cnt: cnt 번째 주사위를 쌓는 중임을 의미한다. (cnt 가 0 : 첫번째 주사위를 쌓는다.)
• total: 주사위 옆면의 숫자 중 가장 큰 숫자들을 합친 값 (모든 층) 
• sideMax: 옆면에 오는 주사위 숫자들 중 가장 큰 값
                  ==> top과 bottom을 제외한 네 숫자중 가장 큰 수이다.

int topIdx = -1;
for (int i = 0; i < 6; i++) {
	if (dices[cnt][i] != top && dices[cnt][i] != bottom) 
		sideMax = Math.max(sideMax, dices[cnt][i]);

	if (dices[cnt+1][i] == top) topIdx = i;
}

// 다음 주사위의 bottom은 이전 주사위의 top이 되어야 한다.(같은 수가 마주봐야 하기 때문)
doStack(dices[cnt + 1][findPair(topIdx)], top, cnt + 1, total + sideMax);

마지막 주사위(N-1번째)를 쌓기 전까지의 코드를 먼저 살펴보면, 크게 3가지 단계로 나뉜다.

1. 옆면의 숫자들 중 가장 큰 수 sideMax에 갱신하기

2. 현재 주사위의 top이 다음 주사위(cnt+1)의 어느 위치(topIdx)인지 찾아내기

3. 다음 주사위 쌓기 

이때, 다음 주사위 bottom은 현재 주사위 top이고, 다음 주사위 top은 다음 주사위 bottom의 Pair가 된다.

첫번째 주사위를 쌓고 두번째 주사위를 쌓는 함수를 호출하는 과정을 살펴보자. 아래 사진이 첫번째와 두번째 주사위의 상태라고 가정한다.

top이 2면, topIdx는 다음 주사위 숫자 2의 i이므로 2가 된다. findIdx(2)를 호출해 4를 얻어온다. dices[1][4] 즉 6이 top이 되고, 2가 bottom이 된다.

doStack(dices[1][4], top, cnt+1, total+sideMax);

==> doStack(6, 2, 1, 6);

		int sideMax = 0;
		if (cnt == N - 1) {
			for (int i = 0; i < 6; i++) {
				if (dices[cnt][i] != top && dices[cnt][i] != bottom) {
					sideMax = Math.max(sideMax, dices[cnt][i]);
				}
			}
			total += sideMax;
			maxNum = Math.max(total, maxNum);
			return;
		}

4. 마지막 주사위를 쌓을 때 코드를 살펴보자

• top과 bottom 을 제외한 옆면 숫자들 중 가장 큰 숫자를 sideMax에 할당해주고, total에 더해 최종 total을 만든다. 
• maxNum은 답이 될 전역 변수로, 주사위를 쌓는 경우의 수 하나가 끝날 때마다 가장 큰 값으로 갱신해준다.

5. maxNum을 출력해준다. 끝.