278. 주사위 윷놀이

아현·2021년 8월 22일
0

Algorithm

목록 보기
291/400

백준






1. Python



import sys

input = sys.stdin.readline

a = [0] * 33
for i in range(21):
    a[i] = i+1
a[21] = 21
a[22], a[23], a[24] = 23, 24, 30 #10에서
a[25], a[26] = 26, 30 //20에서
a[27], a[28], a[29] = 28, 29, 30 
a[30], a[31], a[32] = 31, 32, 20 #30에서

move_in = [0 for _ in range(16)]
move_in[5], move_in[10], move_in[15] = 22, 25, 27 #파란색 칸 다음칸으로 연결

plus = [0 for _ in range(33)] #해당 칸에서 더해줄 숫자
for i in range(1, 21):
    plus[i] = i * 2
plus[22], plus[23], plus[24] = 13, 16, 19
plus[25], plus[26] = 22, 24
plus[27], plus[28], plus[29] = 28, 27, 26
plus[30], plus[31], plus[32] = 25, 30, 35

def dfs(dice_index, ans):
    global max_ans
    if dice_index == 10: //마지막에 갱신
        max_ans = max(max_ans, ans)
        return

    for i in range(4):
        x, x0, move = chess[i], chess[i], dice[dice_index]

        if x == 5 or x == 10 or x == 15:
            x = move_in[x] #이동
            move -= 1 #주사위 수 감소

        if x + move <= 21: 
            x += move #한 번에 이동
        else:
            for _ in range(move):
                x = a[x] #한 칸씩 이동

        if c[x] and x != 21: #다른 말 있으면 제외, 도착지점은 예외
            continue

        c[x0], c[x], chess[i] = 0, 1, x
        dfs(dice_index + 1, ans + plus[x])
        c[x0], c[x], chess[i] = 1, 0, x0

dice = list(map(int, input().split())) #주사위 수
chess = [0] * 4 #말 위치
c = [0] * 33 #말 위치 확인

max_ans = 0
dfs(0, 0)
print(max_ans)

profile
For the sake of someone who studies computer science

0개의 댓글