[BOJ] 17825 주사위 윷놀이 | Python

문제

백준 17825번 주사위 윷놀이 | 골드2

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

17825번: 주사위 윷놀이

• 알고리즘 분류 : 구현 | 브루트포스 알고리즘 | 시뮬레이션 | 백트래킹

 

 

 

풀이 과정

파이썬 풀이

import sys
input = sys.stdin.readline

# 이동할 위치
rotate = [i for i in range(1, 21)]
rotate += [32, 22, 23, 24, 30, 26, 24, 28, 29, 24, 31, 20, 32]

game = []  # 게임판 점수
for s in range(0, 41, 2):
    game.append(s)
game += [13, 16, 19, 25, 22, 24, 28, 27, 26, 30, 35, 0]

dice = list(map(int, input().split()))
horse = [0, 0, 0, 0]  # 말 위치 저장
turn = {5: 21, 10: 25, 15: 27}  # 파란색 칸일 경우 방향 바꾸기(key값에서 value의 인덱스로 이동)
result = 0

def sol(idx, score):
    global result
    if idx >= 10:  # 주사위 10개 다 씀
        result = max(result, score)
        return

    for i in range(4):
        h = horse[i]
        if h in turn:     # 파란색 칸이면 방향 바꿔서 갈 인덱스로
            h = turn[h]
        else:
            h = rotate[h]   # 아니면 rotate에 저장된 값

        for j in range(1, dice[idx]):
            h = rotate[h]   # 해당 주사위 눈 수만큼 이동

        # 도착했거나 말이 겹치지 않아 이동가능하다면
        if h == 32 or (h < 32 and h not in horse):
            tmp = horse[i]
            horse[i] = h
            sol(idx + 1, score + game[h])
            horse[i] = tmp

sol(0, 0)
print(result)

• 구글링을 통해 접한 풀이에서 각색해서 풀었다.
• rotate는 해당 위치에서 한 칸 갈 경우 이동할 위치의 인덱스를, game은 게임판의 점수를 기록하였다.
  방향 이동 없이 2씩 증가하는 점수판 따라 가는 루트, 10 / 20 / 30에서 가는 루트 순으로 저장 
• 이 때, 파란 칸에서는 방향을 바꾸기 때문에 각 칸에서 이동할 인덱스를 딕셔너리 형태로 저장하였다.
  즉, 5번에 도착하면 21(그림의 13점 위치)로, 10번은 25(그림의 22점 위치)로, 15번은 27(그림의 28점 위치)로
• idx는 주사위 10개 중 현재 주사위의 인덱스로, 10이 되면 모든 주사위 다 체크한 것이므로 result를 최대값으로 갱신 
• 4가지 말에 대해 모두 탐색하면서 만약 파란색 칸이면 turn이라는 딕셔너리 사용해서 방향 바꿔주고, rotate를 통해 주사위의 칸 수만큼 바꿔주었다.
  그 다음, 말의 위치를 저장하는 horese의 값 바꿔주고, 점수 더한 뒤 재귀함수 호출해서 다음 주사위에 대해 탐색
• 처음에 rotate를 통해 이동하는 부분이 이해하기 다소 힘들었는데, 직접 수정하면서 진행하다보니 이해하기에 도움이 되었던 것 같다.