백준 알고리즘 17825번 주사위 윷놀이 풀이 With Python

문제 링크: https://www.acmicpc.net/problem/17825

17825번: 주사위 윷놀이

문제는 아래와 같습니다.

막상 문제를 구현하려고 하였을 때 어떻게 해야 할지 막막하였다. 결국 다른 사람들의 풀이를 보았고, 윷놀이 판을 리스트로 구현하였다. 상당히 애를 먹었던 문제다. 풀이는 아래와 같다. DFS(깊이 우선 탐색)을 사용하였고, 백 트레킹을 하여 9번째 주사위에서 현재의 정답에 40을 더한 값보다 작으면 종료시켜서 불필요한 연산을 줄이려고 노력하였다.

import sys


def solution(count, sub, position):
    global answer
    if count == 9 and answer != 0:
        if sub + 40 < answer:
            return
    elif count == 10:
        if answer < sub:
            answer = sub
        return
    for i in range(4):
        x, y = position[i]
        if x == 4 and y == 4:
            continue
        nx, ny = position[i]
        if x == 0:
            if y == 5:
                nx = 1
                ny = -1
            elif y == 10:
                nx = 2
                ny = -1
            elif y == 15:
                nx = 3
                ny = -1
            elif y == 20:
                nx = 4
                ny = 3
        ny += dices[count]
        if nx == 0 and ny >= 20:
            nx = 4
            if ny == 20:
                ny = 3
            else:
                ny = 4
        elif 0 < nx < 4 and ny > len(map1[nx]) - 1:
            ny -= len(map1[nx])
            nx = 4
        elif nx == 4 and ny > 4:
            ny = 4
        if map1[nx][ny] != 0 and [nx, ny] in position:
            continue
        position[i] = [nx, ny]
        solution(count + 1, sub + map1[nx][ny], position)
        position[i] = [x, y]


answer = 0
dices = list(map(int, sys.stdin.readline().split()))
map1 = [
    [],
    [13, 16, 19],
    [22, 24],
    [28, 27, 26],
    [25, 30, 35, 40, 0]
]
for i in range(21):
    map1[0].append(2 * i)
stack = [[0, 0, [[0, 0] for _ in range(4)], [0] * 4]]
solution(0, 0, [[0, 0] for _ in range(4)])
print(answer)