[백준] 2116 - 주사위 쌓기 (자바/Java)

문제

천수는 여러 종류의 주사위를 가지고 쌓기 놀이를 하고 있다. 주사위의 모양은 모두 크기가 같은 정육면체이며 각 면에는 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

출력

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

---

주사위의 6개의 면을 회전시키며 그 중 옆면의 합이 최대인 것을 찾으면 된다.

예를 들어 1번이 가장 밑에 있을 때 옆면의 합이 최대가 되려면 1번과 마주보는 주사위를 제외한 4개의 값 중 최대값을 찾으면 된다.

그렇게 가장 밑의 주사위를 1번부터 6번까지 회전시키며 나온 옆면의 합 중 최대값을 출력하면 된다.

주사위에서 마주보는 면은 A와 F, B와 D, C와 E가 된다.

이걸 배열의 index로 바꾸면 (0, 5) (1, 3) (2, 4)다.

이걸 처리하기 위해 HashMap을 선언하였다.

	static HashMap<Integer, Integer> map = new HashMap<>();

		map.put(0, 5);
		map.put(5, 0);
		map.put(1, 3);
		map.put(3, 1);
		map.put(2, 4);
		map.put(4, 2); // 마주보는 index끼리 서로를 key와 value로 함

 그리고 최대값을 찾기 위해 dfs를 활용하였다.

깊이 depth가 주사위의 크기인 N이 되면 index가 0인 주사위부터 N-1인 주사위까지 모두 더한 것이니 그 합을 max값과 비교하여 업데이트한다.

그리고 N보다 작은 경우에는 해당 depth의 주사위에서 top과 bottom을 찾고, 이것을 제외한 수(옆면) 중 가장 큰 값을 찾아 sum에 더한다.

이를 계속하면 max가 답이 된다.

	static void dfs(int[][] dice, int top, int depth, int sum) {
		if (depth == N) { // 깊이가 N이 되면 계산 완료
			if (sum > max) // max update
				max = sum;
			return;
		}

		// 위 / 아래면 찾기
		int topIdx = 0;
		int bottomIdx = 0;
		for (int d = 0; d < 6; d++) {
			if (dice[depth][d] == top) {
				topIdx = d; // 윗면의 idx 찾기
				bottomIdx = map.get(d); // 윗면과 마주보는 index
			}
		}
		int max = 0;
		for (int d = 0; d < 6; d++) {
			if (d != topIdx && d != bottomIdx) {
				max = Math.max(max, dice[depth][d]);
			}
		} // 옆면 중 최대값 찾아서 더하기

		sum += max;
		// top은 이전 dice의 bottom값
		dfs(dice, dice[depth][bottomIdx], depth + 1, sum);

	}

 

전체 코드

package Gold.g4;

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

public class BOJ_2116_주사위쌓기 {
	static HashMap<Integer, Integer> map = new HashMap<>();
	static int N;
	static int max;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map.put(0, 5);
		map.put(5, 0);
		map.put(1, 3);
		map.put(3, 1);
		map.put(2, 4);
		map.put(4, 2); // 마주보는 index끼리 서로를 key와 value로 함

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

		for (int i = 0; i < 6; i++) {
			dfs(dice, dice[0][i], 0, 0);
		}
		System.out.println(max);

	}

	static void dfs(int[][] dice, int top, int depth, int sum) {
		if (depth == N) { // 깊이가 N이 되면 계산 완료
			if (sum > max) // max update
				max = sum;
			return;
		}

		// 위 / 아래면 찾기
		int topIdx = 0;
		int bottomIdx = 0;
		for (int d = 0; d < 6; d++) {
			if (dice[depth][d] == top) {
				topIdx = d; // 윗면의 idx 찾기
				bottomIdx = map.get(d); // 윗면과 마주보는 index
			}
		}
		int max = 0;
		for (int d = 0; d < 6; d++) {
			if (d != topIdx && d != bottomIdx) {
				max = Math.max(max, dice[depth][d]);
			}
		} // 옆면 중 최대값 찾아서 더하기

		sum += max;
		// top은 이전 dice의 bottom값
		dfs(dice, dice[depth][bottomIdx], depth + 1, sum);

	}

}