[백준] 17825 주사위 윷놀이, python

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

 

 

 

해당 게임판을 그래프로 변환했다.

백트래킹을 통해 각 말의 위치를 계산하고 최댓값을 갱신한다.

말이 도착하는 칸에 다른 말이 있는 경우와 이미 도착한 말은 백트래킹할 때 제외해야 한다.

10,20,30 이 적힌 칸은 파란화살표로 진행해야 하므로 해당칸일 때 처음 1칸은 파란 길로 가야 하므로 flag를 두어 처리했다.

 

import sys
from copy import copy
input = sys.stdin.readline

arr = list(map(int, input().split()))

graph = [[] for _ in range(32)]
score = [0]*32

# 게임판을 그래프로 변환
for i in range(20):
    graph[i].append(i+1)
    score[i] = i*2
graph[5].append(21)
graph[21].append(22)
score[21] = 13
graph[22].append(23)
score[22] = 16
graph[23].append(29)
score[23] = 19

graph[10].append(24)
graph[24].append(25)
score[24] = 22
graph[25].append(29)
score[25] = 24

graph[15].append(26)
graph[26].append(27)
score[26] = 28
graph[27].append(28)
score[27] = 27
graph[28].append(29)
score[28] = 26

graph[29].append(30)
score[29] = 25
graph[30].append(31)
score[30] = 30
graph[31].append(20)
score[31] = 35

graph[20].append(-1)
score[20] = 40


pos = [0,0,0,0] # 현재 말의 위치
answer = 0

def dfs(turn,total):
    global answer, r
    if turn == len(arr):
        answer = max(answer,total)
        return

    moves = arr[turn]

    for i in range(4):
        cur = pos[i]
        if cur == -1:
            continue

        t = 0
        flag = False
        next = cur 

        while t<moves:
            # 이미 말이 도착한경우
            if next == -1:
                break

            if not flag:
                # 10, 20, 30 이 있는 칸은 파란화살표로 가야한다
                if next == 5 or next == 10 or next == 15:
                    next = graph[next][1]

                # 아닌경우 빨간화살표로 진행
                else:
                    next = graph[next][0]

                # 처음 1칸만 빨간길로 갈지 파란길로 갈지 결정, 결정후 flag=True
                flag = True 
                t += 1
                continue

            next = graph[next][0]
            
            t += 1

        # 말이 도착지점이 아닌데 겹치는 경우
        if next != -1 and next in pos:
            continue

        pos[i] = next
        dfs(turn + 1, total if next == -1 else total + score[next])
        pos[i] = cur

dfs(0,0)

print(answer)