[BOJ/Gold 4] 백준 2116 주사위 쌓기(C++)

문제 링크

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

2116번: 주사위 쌓기

문제

천수는 여러 종류의 주사위를 가지고 쌓기 놀이를 하고 있다. 주사위의 모양은 모두 크기가 같은 정육면체이며 각 면에는 1부터 6까지의 숫자가 하나씩 적혀있다. 그러나 보통 주사위처럼 마주 보는 면에 적혀진 숫자의 합이 반드시 7이 되는 것은 아니다.

주사위 쌓기 놀이는 아래에서부터 1번 주사위, 2번 주사위, 3번 주사위, … 의 순서로 쌓는 것이다. 쌓을 때 다음과 같은 규칙을 지켜야 한다: 서로 붙어 있는 두 개의 주사위에서 아래에 있는 주사위의 윗면에 적혀있는 숫자는 위에 있는 주사위의 아랫면에 적혀있는 숫자와 같아야 한다. 다시 말해서, 1번 주사위 윗면의 숫자는 2번 주사위 아랫면의 숫자와 같고, 2번 주사위 윗면의 숫자는 3번 주사위 아랫면의 숫자와 같아야 한다. 단, 1번 주사위는 마음대로 놓을 수 있다.

이렇게 쌓아 놓으면 긴 사각 기둥이 된다. 이 사각 기둥에는 4개의 긴 옆면이 있다. 이 4개의 옆면 중에서 어느 한 면의 숫자의 합이 최대가 되도록 주사위를 쌓고자 한다. 이렇게 하기 위하여 각 주사위를 위 아래를 고정한 채 옆으로 90도, 180도, 또는 270도 돌릴 수 있다. 한 옆면의 숫자의 합의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 주사위의 전개도에서 A, B, C, D, E, F 의 순서로 입력된다. 입력되는 숫자 사이에는 빈 칸이 하나씩 있다. 주사위의 개수는 10,000개 이하이며 종류가 같은 주사위도 있을 수 있다.

그림 1

출력

첫줄에 한 옆면의 숫자의 합이 가장 큰 값을 출력한다.

예제 입력 1

5
2 3 1 6 5 4
3 1 2 4 6 5
5 6 4 1 3 2
1 3 6 2 4 5
4 1 6 5 2 3

예제 출력 1

29

힌트

 

알고리즘 분류

• 구현
• 브루트포스 알고리즘
• 백트래킹

풀이

첫 번째 주사위만 모든 경우의 수를 따지면, 두 번째 주사위부터는 윗면 아랫면이 고정될 수밖에 없다.

그 상태에서 옆면의 4가지 숫자 중 가장 큰 수만 차례차례 더해나간 후 옆면 숫자의 합의 최댓값을 구한다.

코드가 매우 지저분한데 더 깔끔하게 정리하는 방법은 모르겠다.

 

코드

 

#include <iostream>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 10005

using namespace std;
int N;
vector<int> Dice[MAX];
int answer = 0;

int Max_Compare(int A, int B, int C, int D) { // 4개의 숫자 중 최댓값을 출력
	int Arr[3] = { B,C,D };
	int res = A;
	for (int i = 0; i < 3; i++) {
		if (res < Arr[i]) {
			res = Arr[i];
		}
	}
	return res;
}

void Dice_Setting(int Depth, int sum, int Top) {
	if (Depth == N) {
		answer = max(answer, sum);
		return;
	}
	if (Top == -1) { // 첫 번째 주사위라서 아래쪽 주사위 윗면이 정해지지 않은 경우
		for (int i = 0; i < 6; i++) { // 모든 경우의 수를 따진다.
			/* 
				아랫면이 A, 즉 0번째 숫자인 경우 윗면은 F, 즉 5번째 숫자
				아랫면이 B, 즉 1번째 숫자인 경우 윗면은 D, 즉 3번째 숫자
				아랫면이 C, 즉 2번째 숫자인 경우 윗면은 E, 즉 4번째 숫자
			*/
			if (i == 0) {
				int newSum = sum + Max_Compare(Dice[Depth][1], Dice[Depth][2], Dice[Depth][3], Dice[Depth][4]);
				Dice_Setting(Depth + 1, newSum, Dice[Depth][5]);
			}
			else if (i == 1) {
				int newSum = sum + Max_Compare(Dice[Depth][0], Dice[Depth][2], Dice[Depth][4], Dice[Depth][5]);
				Dice_Setting(Depth + 1, newSum, Dice[Depth][3]);
			}
			else if (i == 2) {
				int newSum = sum + Max_Compare(Dice[Depth][0], Dice[Depth][1], Dice[Depth][3], Dice[Depth][5]);
				Dice_Setting(Depth + 1, newSum, Dice[Depth][4]);
			}
			else if (i == 3) {
				int newSum = sum + Max_Compare(Dice[Depth][0], Dice[Depth][2], Dice[Depth][4], Dice[Depth][5]);
				Dice_Setting(Depth + 1, newSum, Dice[Depth][1]);
			}
			else if (i == 4) {
				int newSum = sum + Max_Compare(Dice[Depth][0], Dice[Depth][1], Dice[Depth][3], Dice[Depth][5]);
				Dice_Setting(Depth + 1, newSum, Dice[Depth][2]);
			}
			else if (i == 5) {
				int newSum = sum + Max_Compare(Dice[Depth][1], Dice[Depth][2], Dice[Depth][3], Dice[Depth][4]);
				Dice_Setting(Depth + 1, newSum, Dice[Depth][0]);
			}
		}
	}
	else { // 두 번째 이상 주사위라서 아래쪽 주사위 윗면이 정해진 경우
		int Top_Index;
		for (int i = 0; i < 6; i++) { 
        // Depth - 1번째 숫자의 윗면에 적힌 숫자 Top이 Depth번째 주사위의 어느 면에 있는 숫자인지를 찾는다.
			if (Top == Dice[Depth][i]) {
				Top_Index = i;
				break;
			}
		}
		if (Top_Index == 0) {
			int newSum = sum + Max_Compare(Dice[Depth][1], Dice[Depth][2], Dice[Depth][3], Dice[Depth][4]);
			Dice_Setting(Depth + 1, newSum, Dice[Depth][5]);
		}
		else if (Top_Index == 1) {
			int newSum = sum + Max_Compare(Dice[Depth][0], Dice[Depth][2], Dice[Depth][4], Dice[Depth][5]);
			Dice_Setting(Depth + 1, newSum, Dice[Depth][3]);
		}
		else if (Top_Index == 2) {
			int newSum = sum + Max_Compare(Dice[Depth][0], Dice[Depth][1], Dice[Depth][3], Dice[Depth][5]);
			Dice_Setting(Depth + 1, newSum, Dice[Depth][4]);
		}
		else if (Top_Index == 3) {
			int newSum = sum + Max_Compare(Dice[Depth][0], Dice[Depth][2], Dice[Depth][4], Dice[Depth][5]);
			Dice_Setting(Depth + 1, newSum, Dice[Depth][1]);
		}
		else if (Top_Index == 4) {
			int newSum = sum + Max_Compare(Dice[Depth][0], Dice[Depth][1], Dice[Depth][3], Dice[Depth][5]);
			Dice_Setting(Depth + 1, newSum, Dice[Depth][2]);
		}
		else if (Top_Index == 5) {
			int newSum = sum + Max_Compare(Dice[Depth][1], Dice[Depth][2], Dice[Depth][3], Dice[Depth][4]);
			Dice_Setting(Depth + 1, newSum, Dice[Depth][0]);
		}
	}
}

int main() {
	FIRST
	cin >> N;
	for (int i = 0; i < N; i++) {
		Dice[i].resize(6);
		cin >> Dice[i][0] >> Dice[i][1] >> Dice[i][2] >> Dice[i][3] >> Dice[i][4] >> Dice[i][5];

	}
	Dice_Setting(0, 0, -1); 
    // 처음에는 이전 주사위의 윗면이 정해지지 않은 상태이므로 Top을 -1로 초기화
	cout << answer << "\n";

	return 0;
}