백준 17825 주사위 윷놀이

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

구현문제.
가능한 경우의 수는 10번의 움직임들을 각각의 말에 배치하는 경우인데,
이는 4^10 = 1048576로 모든 경우의 수를 탐색해도 시간초과가 걸리지 않겠다고 생각했다.

주사위 판을 어떻게 잘 설계하느냐가 문제인데, 주사위 판을 그래프라 생각하고 dfs를 한다고 생각하면 된다. dfs는 평소에 설계하던대로 설계하고, 그래프를 이동칸 수 만큼 탐색하면 된다.

import sys
sys.setrecursionlimit(10**5)
arr = list(map(int,input().split()))
graph = [[1], [2], [3], [4], [5], [6, 21], [7], [8], [9], [10], [11, 25], [12], [13], [14], [15], [16, 27], [17], [18], [19], [20], [32], [22], [23], [24], [30], [26], [24], [28], [29], [24], [31], [20], [32]]
score = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 13, 16, 19, 25, 22, 24, 28, 27, 26, 30, 35, 0]
ans = 0
def move(idx,cnt):
    if len(graph[idx]) == 1:
        for i in range(cnt):
            idx = graph[idx][0]
    else:
        for i in range(cnt):
            idx = graph[idx][-1]
    return idx
def dfs(depth,res,idxs):
    global ans
    if depth == 10:
        ans = max(ans,res)
        return
    for i in range(4):
        if idxs[i] == 32: ## 도착 한 말 일때
            continue
        t = move(idxs[i],arr[depth])
        if t == 32:
            tmp = idxs[i]
            idxs[i] = t
            dfs(depth+1,res ,idxs)
            idxs[i] = tmp
            continue
        if t < 32 and t not in idxs:
            tmp = idxs[i]
            idxs[i] = t
            dfs(depth+1,res + score[t],idxs)
            idxs[i] = tmp

dfs(0,0,[0,0,0,0])
print(ans)