[BOJ] 17825 - 주사위 윷놀이 (Python)

 

 

아이디어

 

각 칸에서 이동할 수 있는 칸에 대한 정보를 저장한 후, 현재 턴에서 이동하지 않은 칸으로 이동하며 최대 점수를 구한다.

 

 

풀이

 

board = [
    (0, 1, 2, 3, 4, 5), (2, 2, 3, 4, 5, 6), (4, 3, 4, 5, 6, 7), (6, 4, 5, 6, 7, 8), (8, 5, 6, 7, 8, 9),
    (10, 21, 22, 23, 29, 30), (12, 7, 8, 9, 10, 11), (14, 8, 9, 10, 11, 12), (16, 9, 10, 11, 12, 13),
    (18, 10, 11, 12, 13, 14), (20, 24, 25, 29, 30, 31), (22, 12, 13, 14, 15, 16), (24, 13, 14, 15, 16, 17),
    (26, 14, 15, 16, 17, 18), (28, 15, 16, 17, 18, 19), (30, 26, 27, 28, 29, 30), (32, 17, 18, 19, 20, -1),
    (34, 18, 19, 20, -1, -1), (36, 19, 20, -1, -1, -1), (38, 20, -1, -1, -1, -1), (40, -1, -1, -1, -1, -1),
    (13, 22, 23, 29, 30, 31), (16, 23, 29, 30, 31, 20), (19, 29, 30, 31, 20, -1), (22, 25, 29, 30, 31, 20),
    (24, 29, 30, 31, 20, -1), (28, 27, 28, 29, 30, 31), (27, 28, 29, 30, 31, 20), (26, 29, 30, 31, 20, -1),
    (25, 30, 31, 20, -1, -1), (30, 31, 20, -1, -1, -1), (35, 20, -1, -1, -1, -1), (0, -1, -1, -1, -1, -1)
]

def move(idx, score):
    global res
    if idx > 9:
        if score > res:
            res = score
        return
    visited = set()
    for i in range(4):
        p = pieces[i]
        if p != -1 and p not in visited:
            visited.add(p)
            next_p = board[p][numbers[idx]]
            if next_p == -1 or next_p not in pieces:
                pieces[i] = next_p
                move(idx+1, score+board[next_p][0])
                pieces[i] = p

numbers = tuple(map(int, input().split()))
res = 0
pieces = [0]*4
move(0, 0)
print(res)