[BOJ] Python 백준 주사위 쌓기(2116)

 

 

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

 

제한된 조건 내에 최대 값을 찾는 완전 탐색 문제이다.

백트래킹으로 탐색을 진행했는데 이 코드에서 유심히 봐야할 코드는 조건문이다.

조건에서 0와 5은 서로 반대편이므로 total 값에 사용될 수 없다.

마찬가지로 [1, 3 ] [2,4]는 만약 위,아래 값을 마추는 주사위로 사용되었으면, 사용이 불가능한 인덱스가 되어버린다.

즉, 이전 재귀함수에서 보내준 주사위 윗값이 같은 인덱스를 찾고 그 인덱스와 연관된 ([1, 3 ] [2,4], [0,5]) 값일 경우를 제외한 모든 값중 가장 큰값을 더한 후 다음 재귀로 넘겨주면 된다.

import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline

N = int(input())
s = [list(map(int, input().split())) for _ in range(N)]
max_value = 0

def dfs(n,k,total):
    global max_value
    if n == N:
        max_value = max(max_value, total)
        return

    x = s[n].index(k)
    if x == 0:
        dfs(n+1,s[n][5], total+max(s[n][1],s[n][2],s[n][3],s[n][4]))
    elif x == 1:
        dfs(n+1,s[n][3], total+max(s[n][0],s[n][2],s[n][4],s[n][5]))
    elif x == 2:
        dfs(n+1,s[n][4], total+max(s[n][0],s[n][1],s[n][3],s[n][5]))
    elif x == 3:
        dfs(n+1,s[n][1], total+max(s[n][0],s[n][2],s[n][4],s[n][5]))
    elif x == 4:
        dfs(n+1,s[n][2], total+max(s[n][0],s[n][1],s[n][3],s[n][5]))
    elif x == 5:
        dfs(n+1,s[n][0], total+max(s[n][1],s[n][2],s[n][3],s[n][4]))


for i in range(N):
    if i == 0:
        dfs(1,s[0][5], max(s[0][1],s[0][2],s[0][3],s[0][4]))
    elif i == 1:
        dfs(1,s[0][3], max(s[0][0],s[0][2],s[0][4],s[0][5]))
    elif i == 2:
        dfs(1,s[0][4], max(s[0][0],s[0][1],s[0][3],s[0][5]))
    elif i == 3:
        dfs(1,s[0][1], max(s[0][0],s[0][2],s[0][4],s[0][5]))
    elif i == 4:
        dfs(1,s[0][2], max(s[0][0],s[0][1],s[0][3],s[0][5]))
    elif i == 5:
        dfs(1,s[0][0], max(s[0][1],s[0][2],s[0][3],s[0][4]))


print(max_value)

 

회고,

주사위라는 정해진 6개의 값이라는 점을 고려 못하고, 모든 루프문을 돌며 조건 처리를 할 생각을 하고 있었다.

때로는 그냥 저렇게 모든 조건문을 적어서 처리하는 법이 더 효율적일 수 있다는 점을 염두해둬야 겠다.