[Python] 백준 17825: 주사위 윷놀이

www.acmicpc.net/problem/17825

17825번: 주사위 윷놀이

풀이 방법

• 윷놀이 판을 직접 만들어야 해서 좀 귀찮은 문제였다. 윷놀이 판 만드는 거 빼면 평범한 백트래킹 문제다.
• 윷놀이 판에 각각 인덱스를 매기고 graph로 만들어줘서 이동할 수 있는 인덱스를 저장했다. 예를들어 0번이 출발점이고 다음칸이 1번이라면 graph[0] = [1], 5번 칸에서는 갈 수 있는 칸이 2칸 이므로 graph[5] = [6, 21]과 같이 표현해줬다. 
• 각 칸의 점수도 배열로 저장해놔야 한다. 
• backtracking으로 입력 받은 주사위 순서에 대해서 각각 몇 번말이 이동할지 부르트포스로 모든 경우의 수를 계산한다. 

전체 코드

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]
dice = list(map(int, input().split()))
answer = 0
def backtracking(loc, result, horse, test):
    global answer
    if loc >= 10:
        answer = max(answer, result)
        return
    for i in range(4):
        x = horse[i]
        if len(graph[x]) == 2:
            x = graph[x][1]
        else:
            x = graph[x][0]
        for j in range(1, dice[loc]):
            x = graph[x][0]
        if x == 32 or (x < 32 and x not in horse):
            before = horse[i]
            horse[i] = x
            test.append(x)
            backtracking(loc + 1, result+score[x],horse, test)
            test.pop()
            horse[i] = before
backtracking(0, 0, [0,0,0,0], [])
print(answer)