[백준, Java] 2116번, 주사위 쌓기 알고리즘 분류(구현, 브로트포스)

문제 링크

2116번: 주사위 쌓기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

1. 1번째 주사위는 마음대로 놓을 수 있으며, 그 외에 주사위는 문제에 설명한 것처럼 제한된다.

2. 주사위는 위 아래를 고정하고, 90도, 180도, 270도로 돌릴 수 있습니다.

3. 하나의 옆면의 숫자의 합의 최대값을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 모든 첫 주사위 위치를 기준으로 재귀 탐색으로 옆면의 최대값을 탐색합니다.

 

3. 최대값을 결과로 출력합니다.

 

주사위가 마주보는 면

 

 

[A] ↔ [F] : 0 ↔ 5

 

[B] ↔ [D] : 1 ↔ 4

 

[C] ↔ [E] : 2 ↔ 3

 

 

재귀 탐색하기.

 

아래에 놓인 주사위를 기준으로 순차적으로 다음 주사위를 쌓습니다.

 

옆면은 회전이 가능하기 때문에 윗면과 아랫면을 제외한 최대값을 더해나아가면 됩니다.

 

※ 예제입력 진행되는 과정을 보시면 이해하시기 편하실 것입니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

N = 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

 

2. 모든 첫 주사위 위치를 기준으로 재귀 탐색으로 옆면의 최대값을 탐색합니다.

※정답이 되는 경우만 시뮬레이션을 진행하겠습니다.

 

1번째 주사위

 

윗면 : 1

 

아랫면 : 5

 

초록 : 아랫면

보라 : 윗면

 

2 3 1 6 5 4 : 1번째 주사위 가장 큰 옆 면 : 6

 

3 1 2 4 6 5 : 2번째 주사위 가장 큰 옆 면 : 6

 

5 6 4 1 3 2 : 3번째 주사위 가장 큰 옆 면 : 6

 

1 3 6 2 4 5 : 4번째 주사위 가장 큰 옆 면 : 6

 

4 1 6 5 2 3 : 5번째 주사위 가장 큰 옆 면 : 5

 

 

3. 최대값을 결과로 출력합니다.

 

6 + 6 + 6 + 6 + 5 = 29

29을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 주사위의 각 면의 숫자를 나누었습니다.
• 각 주사위의 상태를 기준으로 search함수로 재귀 탐색을 진행합니다.
• 모든 재귀 탐색이 종료한 뒤 옆면의 최대값을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• setting함수는 주사위를 순차적으로 쌓는 재귀 함수입니다.
• pairCheck함수는 마주보는 면의 index를 반환하는 함수입니다.

 

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static int max = -1, N;
    static int[][] arr;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        arr = new int[N][6];
        //N개의 주사위 정보 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<6;j++)
                arr[i][j] = Integer.parseInt(st.nextToken());
        }
        //1번째 주사위 상태에 따른 재귀 탐색 진행
        for(int i=0;i<6;i++) {
            search(1, i, 0);
        }
        bw.write(String.valueOf(max));	//최대값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //주사위를 순차적으로 쌓는 재귀 함수
    static void search(int cnt, int bottom, int sum){
        //아랫면을 마주보는 면 구하기
        int pair = pairCheck(bottom);
        int tempMax = -1;
        //옆면의 최대값 구하기
        for(int i=0;i<6;i++){
            if(i == pair || i == bottom)
                continue;
            tempMax = Math.max(tempMax, arr[cnt-1][i]);
        }
        sum += tempMax;	//최대값 더하기
        //주사위를 모두 다 쌓았을 때
        if(cnt == N){
            max = Math.max(max, sum);	//최대값 비교
            return;
        }
        //다음 주사위 쌓기 진행
        for(int i=0;i<6;i++){
            if(arr[cnt-1][pair] == arr[cnt][i]){
                search(cnt+1, i, sum);
                break;
            }
        }
    }
    //마주보는 면 인덱스 구하는 함수
    static int pairCheck(int n){
        if(n == 0)
            return 5;
        else if(n == 1)
            return 3;
        else if(n == 2)
            return 4;
        else if(n == 3)
            return 1;
        else if(n == 4)
            return 2;
        else
            return 0;
    }
}