백준 17825번: 주사위 윷놀이 (Python)

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

17825번: 주사위 윷놀이

접근

dfs 알고리즘을 이용하여 각 주사위가 몇번 말에 할당되는지 모든 경우의 수를 고려하여 가장 큰 값이 나오는 결과값을 구할 수 있다.

처음에는 리스트로 경로를 만들어 재귀를 통해 문제를 해결하려 하였는데 이동하는 경로를 표시하기가 복잡하여,
각 위치에서 주사위가 나왔을 때의 이동 후 위치 값을 저장하는 딕셔너리를 이용하는 방법으로 선회하여 문제를 해결하였다.

재귀하는 과정에서는 말이 마지막 위치에 도달했을 때를 구분하는 코드만 추가한 간단한 수준의 dfs 함수를 이용했다.

코드

from copy import deepcopy

dice = list(map(int, input().split()))
# board_dict  k: location, v: next_location_list([dice_1, dice_2, dice_3, dice_4, dice_5])
board_dict = {}
# 말이 이동하여 보드판 바깥으로 나갈 경우 -1로 표기
for i in range(21):
    tmp = []
    for j in range(1, 6):
        tmp.append(i + j if i + j < 21 else -1)
    board_dict[i] = tmp
board_dict[5] = [21, 22, 23, 29, 30]
board_dict[21] = [22, 23, 29, 30, 31]
board_dict[22] = [23, 29, 30, 31, 20]
board_dict[23] = [29, 30, 31, 20, -1]
board_dict[10] = [24, 25, 29, 30, 31]
board_dict[24] = [25, 29, 30, 31, 20]
board_dict[25] = [29, 30, 31, 20, -1]
board_dict[15] = [26, 27, 28, 29, 30]
board_dict[26] = [27, 28, 29, 30, 31]
board_dict[27] = [28, 29, 30, 31, 20]
board_dict[28] = [29, 30, 31, 20, -1]
board_dict[29] = [30, 31, 20, -1, -1]
board_dict[30] = [31, 20, -1, -1, -1]
board_dict[31] = [20, -1, -1, -1, -1]
# score_dict  k: location, v: score
score_dict = {
    21: 13,
    22: 16,
    23: 19,
    24: 22,
    25: 24,
    26: 28,
    27: 27,
    28: 26,
    29: 25,
    30: 30,
    31: 35,
    -1: 0,
}
for i in range(1, 21):
    score_dict[i] = i * 2
locations = [0] * 4
ans = []


def dfs(prev_number, location_list, depth):
    if len(dice) <= depth:
        # 말의 모든 이동이 끝날 경우 총 합을 ans에 추가
        ans.append(prev_number)
        return
    for i in range(4):
        if location_list[i] == -1:
            # 말이 도착점에 있을 경우 continue
            continue
        ne_lo = board_dict[location_list[i]][dice[depth] - 1]
        next_location = deepcopy(location_list)
        if ne_lo != -1 and ne_lo in location_list:
            # 말이 이동하려는 위치에 다른 말이 있을 경우 continue
            continue
        next_location[i] = ne_lo
        dfs(prev_number + score_dict[next_location[i]], next_location, depth + 1)


dfs(0, locations, 0)
print(max(ans))

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!