python 백준 17825 주사위 윷놀이

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

로직

• 말은 4개에 주사위를 총 10번을 던지므로 전체 경우의 수는 4^10로 약 100만

• 그렇기에 모든 경우의 수를 확인해도 문제가 발생하지 않음

• 길을 총 5개로 분류

  • 0번 : 가장 길게 돌아가는 길
  • 1번 : 10점부터 25점 사이의 지름길
  • 2번 : 20점부터 25점 사이의 지름길
  • 3번 : 30점부터 25점 사이의 지름길
  • 4번 : 25점부터 종점 사이의 지름길

• shortcut에 빠지는 곳은 전부 10의 약수이므로 이를 이용하여 길을 옮겨타는 방식

  • 이 때 포인트가 30점인 곳은 두곳이므로 0번 길인지를 확인하고 shortcut으로 갈아타야함

def recur(turn,maxTurn,player,totalPoint):
    global dice,root,check,maxPoint
    if turn == maxTurn:
        maxPoint = max(maxPoint,totalPoint)
        return

    cnt = dice[turn]
    for p in range(len(player)):
        if player[p-1] == [0,0]:
            break

        r,c = player[p]
        # 도달 체크
        if r == -1:
            continue
        nr = r
        nc = c + cnt

        # 현제 root에서 벗어나는지 체크
        if nc < len(root[r]):
            getPoint = root[nr][nc]
            # 숏컷 체크
            if nr == 0 and getPoint % 10 == 0:
                nr = getPoint//10
                nc = 0

            # 중복 위치 체크
            if check[nr][nc]:
                player[p] = [nr,nc]
                check[nr][nc] = False   # 이동 위치 이동 불가
                check[r][c] = True  # 기존 위치 이동 가능

                # 다음턴
                recur(turn+1,maxTurn,player,totalPoint+getPoint)
                player[p] = [r,c]
                check[nr][nc] = True
                check[r][c] = False

            else:
                continue

        # 마지막 길로 이동 or 도착
        else:
            # 마지막 길에서 넘겼을 경우
            if nr == 4:
                player[p] = [-1,-1]
                check[r][c] = True
                recur(turn+1,maxTurn,player,totalPoint)
                player[p] = [r,c]
                check[r][c] = False
            else:
                nr = 4
                nc -= len(root[r])
                if r == 0:
                    nc += 3
                # 결국 도착 할 경우
                if nc >= len(root[nr]):
                    player[p] = [-1,-1]
                    check[r][c] = True
                    recur(turn+1,maxTurn,player,totalPoint)
                    player[p] = [r,c]
                    check[r][c] = False

                elif check[nr][nc]:
                    getPoint = root[nr][nc]

                    player[p] = [nr,nc]
                    check[r][c] = True
                    check[nr][nc] = False
                    recur(turn+1,maxTurn,player,totalPoint+getPoint)
                    player[p] = [r,c]
                    check[r][c] = False
                    check[nr][nc] = True

# 10의 배수마다 shortcut

dice = list(map(int,input().split()))
root = [[2*i for i in range(20)],[10,13,16,19],[20,22,24],[30,28,27,26],[25,30,35,40]]
check = [[True]*20,[True]*4,[True]*3,[True]*4,[True]*4]
player = [[0,0],[0,0],[0,0],[0,0],[-1,-1]]
maxPoint = 0
recur(0,10,player,0)
print(maxPoint)