[Day25]JAVA 백준 주사위쌓기(2116번)

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

 

백준 주사위 쌓기 문제는 완전탐색으로 모든 경우의 수를 탐색하고 그 중 최대값 을 구하는 방식으로 해결할 수 있다. 

 

🌘문제 이해하기

• n개의 주사위를 쌓는다.
• 서로 붙어 있는 두 개의 주사위에서 아래에 있는 주사위의 윗면에 적힌 숫자는 위에 있는 주사위의 아랫면에 적혀있는 숫자와 같아야 한다. 

 n+1번째 주사위 아랫면 숫자 = n번째 주사위 윗면 숫자

• n개씩 주사위를 쌓아 놓으면 긴 사각 기둥이 된다. 
• 사각 기둥의 4개의 옆면 중에서 어느 한면의 숫자의 합이 최대가 되도록 주사위를 쌓고자 한다. 
• 첫번재 줄에는 주사위의 개수가 입력 그다음 줄부터는 한줄에 하나씩 주사위의 각 면에 적혀진 숫자가 A,B,C,D,E,F, 순서로 입력된다. 

---

🌗문제 자세히보기

주사위의 구조에 대해 이해를 해야한다. 
주사위의 각 면들은 (A-F) , (B-D) , (C-E) 형태로 서로 마주보는 형식이다(무조건!!)
이를 숫자로 계산하면 주사위의 각 면을 0부터5까지라고 하면 (0-5) , (1-3) , (2-4) 이다. (배열에 값 넣기 편하게...0부터 시작)

이규칙을 이해하면 각 주사위의 윗면 , 아랫면을 구할 수 있다.

주사위의 윗면 아랫면에 오는 숫자들은 아래와 같은 규칙들로 정의된다.

1번째 윗면 숫자 = 2번째 아랫면 숫자
2번째 윗면 숫자 = 3번째 아랫면 숫자
3번째 윗면 숫자 = 4번째 아랫면 숫자
4번째 윗면 숫자 = 5번째 아랫면 숫자...

다음 주사위의 아랫면의 숫자를 알 수 있으니 해당 아랫면이 몇번째에 오는 면인지를 확인하고 위의 주사위의 구조를 파악하여 윗면도 구할 수 있다. 
윗면,아랫면이 몇번째 면들인지 구하였으면 이 면들을 제외하고 나머지 면들 중 가장 큰 면의 숫자가 해당 주사위에서 만들 수 있는 가장 큰 숫자이다.
이러한 방식을 모든 주사위에 적용하면서 가장 큰 면의 숫자를 구해준다.

가능한 모든 수를 계산하기 위해서는 첫번째 주사위의 6면 중 한면이 윗면일때 로 지정하고 6번 탐색하는 것이다.

 

정리하면  
1. 1번째 주사위의 윗면 정하기 (몇번째 면인지)
2. 주사위의 윗면 과 아랫면이 몇번째 면인지를 확인한다.
3. 윗면 , 아랫면을 제외한 면들 중 가장 큰 면의 숫자를 구한다.
4. 다음 주사위의 아랫면은 위의 주사위의 윗면과 동일한 숫자이다. 이를 기준으로 다음주사위의 윗면을 구한다.
5. 2번으로 돌아가서 n번째 주사위까지 가장 큰 면을 구하여 모든면의 합을 구한다.
6. 1번으로 돌아가서 1번째 주사위의 윗면 다시 정한다(주사위는 총 6면임으로 6번의 윗면을 기준으로 조회) 

---

import java.io.*;
import java.util.*;
public class Main{ 
    static int answer = 0;
    public static void main(String[] args) throws IOException
    { 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); //주사위 개수

        //주사위 정보 저장
        ArrayList<int[]> dice = new ArrayList<>();

        for(int i=0;i<n;i++)
        {
            dice.add(new int[6]);
        }

        for(int i=0;i<n;i++)
        {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] diceCnt = dice.get(i);

            for(int j=0;j<6;j++)
            {
                diceCnt[j] = Integer.parseInt(st.nextToken());
            }
        }

        //첫번째 주사위를 기준으로 윗값을 구한다.       
        int maxSum = Integer.MIN_VALUE;

        for(int i=0;i<6;i++)
        {  
            int totSum = DFS(dice,i,0,0);
            maxSum = Math.max(maxSum,totSum);           
        }

        System.out.println(maxSum);

    }    

    //ArrayList<int[]> dice  : 주사위 정보가 들어있는
    //int up : 기준이 되는 윗면 번호(A,B,...)
    //int upSide : 기준이 되는 윗면에 올 숫자
    //int diceCnt : 몇번째 주사위
    //int sum : 지금까지 가장 높은 면의 숫자를 더한값
    public static int DFS(ArrayList<int[]> dice , int up , int diceCnt , int sum)
    {
        while(diceCnt < dice.size()){

            int downSide = 0; //해당 면에 오는 값
            int down = 0; //해당 면이 몇번째 면인지
           
            //1. 윗면 하나를 선택 아랫면 확인
            //짝궁 (1-6) | (2-4) | (3-5)
            switch (up) {
                case 0:
                    down = 5;
                    break;
                case 1:
                    down = 3;
                    break;
                case 2:
                    down = 4;
                    break;
                case 3:
                    down = 1;
                    break;
                case 4:
                    down = 2;
                    break;
                case 5:
                    down = 0;
                    break;
            }
         
            //하나의 주사위 정보
            int[] diceInfo =dice.get(diceCnt); 

            //아랫면에 오는 숫자    
            downSide = diceInfo[down];  

            int maxNum = Integer.MIN_VALUE;
            
            //2. 윗면 아랫면을 제외한 나머지 면 의 값들 확인 후 최고값 구하기
            for(int i=0;i<6;i++)
            {
                if( i == up || i == down)
                    continue;

                maxNum = Math.max(maxNum,diceInfo[i]); //남은 면 중 가장 높은 값 저장   
            }

            //한 면 씩 더하기
            sum += maxNum; 

            //3. 기존의 아랫면 은 다음 주사위의 윗면 숫자가 된다. 이를 바탕으로 다음주사위의 윗면 번호 구하기
            if(diceCnt <dice.size()-1)
            {
                int[] nextDiceInfo =dice.get(diceCnt+1);
                for(int i=0;i<nextDiceInfo.length;i++)
                {
                    if(nextDiceInfo[i] == downSide)
                    {
                        //다음 주사위 윗면이 몇번째 면인지 구하기
                        up = i;
                        break;
                    }
                }
            }  

            diceCnt++;  
        }

        return sum;        
    }   
}