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

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

문제

주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다.

 

• 처음에는 시작 칸에 말 4개가 있다.
• 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다.
• 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.
• 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
• 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.

주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구해보자.

입력

 

첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

예제 입력 1 

1 2 3 4 1 2 3 4 1 2

예제 출력 1 

190

예제 입력 2 

1 1 1 1 1 1 1 1 1 1

예제 출력 2 

133

예제 입력 3 

5 1 2 3 4 5 5 3 2 4

예제 출력 3 

214

예제 입력 4 

5 5 5 5 5 5 5 5 5 5

예제 출력 4 

130

 

⭕ CODE

import sys

sys.stdin = open('input.txt')

input = sys.stdin.readline

def check(count, s):
    global result

    # 10턴 사용했으면
    if count == 10:
        # 점수의 최댓값 갱신
        if s > result:
            result = s
        return result

    # i번 말
    for i in range(4):
        # i번 말의 현재 위치
        now = dice[i]

        # 더이상 주사위를 굴릴 수 없는 곳이면 넘긴다
        if now == -1:
            continue

        # 현재 움직여야하는 이동 거리
        now_move_distance = arr[count]

        # 다음번 i번의 말이 위치하는 위치 인덱스
        # yut[now] : 지금 i번 말이 위치해있는 인덱스에서 갈 수 있는 인덱스
        # yut[now][now_move_distance - 1] : 다음 도착지점
        next = yut[now][now_move_distance - 1]

        # 도착지점이 아니고 이미 그 자리에 다른 말이 있다면 넘긴다
        if next != -1 and next in dice:
            continue

        # 만약 도착지점이라면 점수는 없다
        if next == -1:
            # 방문처리
            dice[i] = next
            # dfs 실행
            # 점수는 늘어나지 않지만 횟수만 증가한다.
            check(count + 1, s)
            # 방문처리 초기화
            dice[i] = now
            continue

        # 방문처리
        dice[i] = next
        # 도착지점의 점수를 더해주고 횟수 + 1
        check(count + 1, s + score[next])
        # 방문처리 초기화
        dice[i] = now

# 말의 개수 4개
# 파란색 칸은 파란 화살표로 이동한다
# 이동했을 때 다른 말이 존재한다면 그 말은 선택 불가능 하지만
arr = list(map(int, input().split()))

# 각 인덱스에서 주사위 1,2,3,4,5 마다 갈 수 있는 인덱스
yut = {0: [1, 2, 3, 4, 5],
       1: [2, 3, 4, 5, 6],
       2: [3, 4, 5, 6, 7],
       3: [4, 5, 6, 7, 8],
       4: [5, 6, 7, 8, 9],
       5: [22, 23, 24, 25, 26],
       6: [7, 8, 9, 10, 11],
       7: [8, 9, 10, 11, 12],
       8: [9, 10, 11, 12, 13],
       9: [10, 11, 12, 13, 14],
       10: [28, 29, 25, 26, 27],
       11: [12, 13, 14, 15, 16],
       12: [13, 14, 15, 16, 17],
       13: [14, 15, 16, 17, 18],
       14: [15, 16, 17, 18, 19],
       15: [30, 31, 32, 25, 26],
       16: [17, 18, 19, 20, -1],
       17: [18, 19, 20, -1, -1],
       18: [19, 20, -1, -1, -1],
       19: [20, -1, -1, -1, -1],
       20: [-1, -1, -1, -1, -1],
       21: [-1, -1, -1, -1, -1],
       22: [23, 24, 25, 26, 27],
       23: [24, 25, 26, 27, 20],
       24: [25, 26, 27, 20, -1],
       25: [26, 27, 20, -1, -1],
       26: [27, 20, -1, -1, -1],
       27: [20, -1, -1, -1, -1],
       28: [29, 25, 26, 27, 20],
       29: [25, 26, 27, 20, -1],
       30: [31, 32, 25, 26, 27],
       31: [32, 25, 26, 27, 20],
       32: [25, 26, 27, 20, -1]
       }

# index 별 점수
score = {
    0: 0,
    1: 2,
    2: 4,
    3: 6,
    4: 8,
    5: 10,
    6: 12,
    7: 14,
    8: 16,
    9: 18,
    10: 20,
    11: 22,
    12: 24,
    13: 26,
    14: 28,
    15: 30,
    16: 32,
    17: 34,
    18: 36,
    19: 38,
    20: 40,
    21: 0,
    22: 13,
    23: 16,
    24: 19,
    25: 25,
    26: 30,
    27: 35,
    28: 22,
    29: 24,
    30: 28,
    31: 27,
    32: 26,
}

result = 0

# 각 말들의 현재 위치를 나타내는
dice = [0, 0, 0, 0]

check(0, 0)

print(result)

✏️ Comment

위 그림처럼 인덱스를 지정하고 각각의 인덱스에서 주사위 1,2,3,4,5가 나오면 어느 인덱스로 갈 수 있는지 작성하고 
인덱스 마다의 점수를 나타내는 과정에서 실수가 발생하였다.