BOJ_2116_주사위쌓기_JAVA
문제 : 주사위쌓기
링크 : BOJ_2116_주사위쌓기
접근 방식
규칙 깔리는 주사위의 윗면과 놓는 주사위의 밑면의 숫자가 같아야한다.
ABCDEF 순으로 값이 주어진다.
순서는 1번 주사위부터 N번주사위까지 주어짐
A-F, B-D, C-E가 윗면, 아랫면이 될 수 있다. 이 세가지 경우를 조사해
경우의 수 별로 나머지 주사위들의 최댓값을 모아 출력하면 될 것 같았다. 하지만 모든 경우의 수를 따지려면, 주사위 개수만큼 for문을 중첩해야 할 것 같았다. 따라서 재귀를 이용해서 풀어보기로 했다.
주사위를 숫자로 매칭했을 때 다음과 같다. 1-A, 2-B, 3-C, 4-D, 5-E, 6-F
그리고, 어느 한 쪽을 주사위의 밑면으로 한다면 그 반대편 의 index는 다음과 같다. 1-6, 2-4, 3-5
1번에서 먼저 1번 주사위를 선택한다. 그 다음부터는 주사위를 쌓는 방향을 바꿀수 없다. 첫 주사위의 방향대로 나머지 주사위의 옆면의 수가 정해진다.
이게 DFS가 맞는지는 모르겠지만 1번주사위부터 6번주사위까지 경우의 수를 한 번씩 모두 구하는 것이라고 생각해서 DFS라고 이름지었다.
함수의 실행은 대략 이렇게 이루어진다.
먼저 주사위를 놓으면 반대편 주사위까지는 사용을 못한다.
나머지 주사위 값 중에서 최댓값을 구해 더하고, 다음 주사위로 넘어간다. 반대편 주사위의 값을 다음 재귀로 넘겨준다.
풀이 방법
-
주사위 개수를 읽어와 변수에 저장한다. 주사위 정보는 2차원 배열을 생성하여 저장한다.
-
i를 1부터 6까지 반복한다. 여기서 1~6은 첫 번째 주사위의 바닥에 두는 수를 뜻한다. 반복할 때마다 dfs 메서드를 호출한다.
-
dfs 메서드는 인자값으로 int 타입과 1차원 배열을 받는다. int 타입에는 바닥에 놓을 1번주사위의 값이, 배열에는 1번 주사위의 정보가 주어진다.
-
먼저 6의 크기의 1차원 boolean 배열을 선언한다. 그 후, 인자값으로 받아온 주사위 정보를 탐색하여 해당 밸류를 가지고 있는 index를 찾아 저장한다.
-
규칙(1-6, 2-4, 3-5)대로, 밑면과 밑면의 대응되는 윗면을 visited 배열에서 방문처리한다. 해당 규칙은 따로 메서드(search 메서드)로 꺼내두었다.
-
1부터 6까지 반복한다. 만약 해당 위치가 이미 방문한 상태라면 continue하고, 아닐 경우 주사위의 나머지 값 중에서 최댓값을 구해 저장한다.
-
해당 최댓값을 누적시키고 재귀호출한다. 재귀호출하는 인자값으로는 현재 놓여진 주사위의 윗면의 index, 그리고 다음 주사위의 배열을 인자값으로 넘겨준다.
-
기저조건으로는 cnt가 N-1이 되었을 때, 즉 N번 주사위까지 탐색이 되었을 때 재귀가 종료된다.
-
1번 dfs를 돌릴 때마다 1면을 바닥으로 했을 때의 최댓값이 나타난다. 즉, 6번 dfs를 돌리면서 최댓값을 저장하면 주사위 N개를 쌓아올릴때의 옆면의 최댓값을 구할 수 있다.
-
구한 최댓값을 출력한다.
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BOJ_2116_주사위쌓기 {
/* 규칙 깔리는 주사위의 윗면과 놓는 주사위의 밑면의 숫자가 같아야한다.
* ABCDEF 순으로 값이 주어짐. A는 윗면, F는 아랫면
* 순서는 1번 주사위부터 6번주사위까지 주어짐
* A-F, B-D, C-E가 윗면, 아랫면이 될 수 있다. 이 세가지 경우를 조사해
* 경우의 수 별로 나머지 주사위들의최댓값을 모아 출력하면 되지않을까
* */
static int max, sum, N;
static int arr[][];
static int cnt = 0;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(in.readLine());
arr = new int[N][6];
StringTokenizer st;
for(int i=0;i<N;i++) {
st = new StringTokenizer(in.readLine()," ");
for(int j=0;j<6;j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
// 1-A, 2-B, 3-C, 4-D, 5-E, 6-F
// 1-6, 2-4, 3-5
// 1-6 제외
// 1번에서 가장 작은 수를 먼저 바닥으로 쓰면 그 반대편의 수는 다음 사람은 못쓴다.
// 굳이 가장 작은수를 바닥으로 쓸 필요없이 6만 남길 수 있으면 된다.
// 먼저 1번 주사위를 선택한다.(숫자 자유)그 다음부터는 그냥 바꿀수 없이 정해짐
// dfs를 해보자
// 먼저 주사위를 놓으면 반대편 주사위까지는 사용을 못한다.
// 나머지 주사위 값 중에서 최댓값을 구해 더하고, 다음 주사위로 넘어간다. 반대편 주사위의 값을 다음 재귀로 넘겨준다.
for(int i=1;i<=6;i++) {
sum = 0;
cnt = 0;
dfs(i,arr[0]);
max = Math.max(max, sum);
}
System.out.println(max);
}
public static void dfs(int value,int dice[]) {
int index = 0;
boolean[] visited = new boolean[6];
for(int i=0;i<6;i++) {
if(dice[i] == value) {
index = i;
// System.out.println(i);
}
}
visited[index] = true;
visited[search(index)] = true;
// System.out.println(index+":"+search(index)+":"+value+":"+cnt);
int max = 0;
for(int i=0;i<6;i++) {
if(visited[i] == true) {
continue;
}
max = Math.max(max, dice[i]);
}
// System.out.println(Arrays.toString(visited));
sum = sum + max;
if(cnt == N-1) {
// System.out.println(sum);
return;
}
dfs(dice[search(index)],arr[++cnt]);
}
public static int search(int index) {
switch(index) {
case 0:
return 5;
case 1:
return 3;
case 2:
return 4;
case 3:
return 1;
case 4:
return 2;
case 5:
return 0;
}
return -1;
}
}