[BOJ] 2116 - 주사위 쌓기

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

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

2116번: 주사위 쌓기

난이도: 골드 4

사용언어: JAVA

 

풀이

주사위를 이용한 구현문제이자 모든 경우의 수를 테스트 해보아야하는 브루트포스 문제입니다.

 

구현 로직은 다음과 같습니다.

 

1. 가장 아랫쪽 주사위는 마음대로 둘 수 있으므로 6면을 모두 테스트한다.

2. 두 번째 주사위부터는 아랫쪽 주사위의 윗면과 현재 주사위의 아랫면을 같은 수로 맞춰준다.

3. 아랫면과 윗면을 제외한 가장 큰 수를 해당 주사위에서 나올 수 있는 최대 측면값으로 저장한다.

4. 마지막 주사위까지 쌓은 후 각 주사위의 측면에 올 수 있는 최댓값을 모두 더해준다.

 

어려운 로직이 아니기 때문에 많은 시간을 들일 필요는 없을 것이라 생각합니다.

 

아래는 제가 작성한 코드입니다.

 

import java.io.*;
import java.util.*;
 
class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int[][] dice;
    static int N;
    static int[] opposite = {5, 3, 4, 1, 2, 0}; // 주사위 반대방향
    static int[] max; // 각 주사위별 최댓값 저장
    static int result = 0; // 전체 경우의 수에 대한 최댓값 저장
 
    public static void dfs(int bottom, int cnt) { // bottom: 현재 주사위 아랫쪽 면, cnt: 현재 쌓은 주사위 갯수
        int top = opposite[bottom]; // top: 현재 주사위 윗쪽 면
        int next_bottom = -1; // 다음 주사위의 아랫쪽 면
 
        for (int i = 0; i < 6; i++) {
            if (i == bottom || i == top) { // 현재 주사위의 아랫쪽 면과 윗쪽 면을 제외하고,
                continue;
            }
 
            max[cnt] = Math.max(max[cnt], dice[cnt][i]); // 가장 큰 수를 max 배열에 저장 (n번째 주사위의 측면 최댓값을 n번 인덱스에 저장)
        }
 
        if (cnt == N - 1) { // 마지막 주사위까지 다 쌓았으면,
            int sum = 0;
            for (int i = 0; i < N; i++) { // 현재 max 배열에 있는 모든 수를 더해준다. (각 주사위 별 측면 최댓값을 모두 더해준 것.)
                sum += max[i];
            }
            result = Math.max(result, sum); // 전체 최댓값 갱신
            return;
        }
 
        for (int i = 0; i < 6; i++) { // 다음 쌓을 주사위의 아랫면을 찾아서
            if (dice[cnt][top] == dice[cnt + 1][i]) {
                next_bottom = i;
            }
        }
        dfs(next_bottom, cnt + 1); // 재귀함수를 통해 다음 주사위를 쌓아준다.
    }
 
    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        dice = new int[N][6]; // 주사위 입력
        max = new int[N]; 
 
        for (int i = 0; i < N; i++) {
            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++) { // 첫 주사위는 마음대로 놓을 수 있기 때문에 6가지 면 모두 테스트
            Arrays.fill(max, 0);
            dfs(i, 0);
        }
 
        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
        br.close();
    }
}