백준 17825 주사위 윷놀이 (파이썬)

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

17825번: 주사위 윷놀이

문제에 주어진 윷놀이판을 그대로 잘 구현하고 dfs로 중복순열을 구현하여 모든 경우의 수를 다 구하면된다

 

1. 빨간 화살표를 따라 시작부터 도착까지 외곽을 도는 경로의 인덱스는 0부터 21

   10에서 안으로 들어가는 경로의 인덱스는 22, 23 24

   20에서 안으로 들어가는 인덱스는 25, 26

   30에서 안으로 들어가는 인덱스는 30, 31, 32로 정하고 윷놀이판 a를 만든다

   a의 값은 다음 칸에 대한 인덱스이고 도착에 해당하는 21은 해당 지점을 계속 반복한다

2. a에서 5, 10, 15에 해당하는 인덱스는 파란색 칸이므로 경로를 따로 설정해야 한다

   move_in의 5, 10, 15번 인덱스에서 안쪽 다음칸에 해당하는 인덱스를 연결한다

3. plus는 해당 칸에서 더해줄 숫자이다

4. dice에는 입력받은 주사위 수, chess는 말의 위치, c는 해당 지점에 말이 있는지 확인하는 배열이다

5. dfs로 4^10 중복순열을 구현하여 모든 케이스를 검사해본다

6. 만약 현재 이동할 말의 위치가 파란색 칸이면 move_in을 불러와 한 칸 미리 이동한다

   주사위 수에 해당하는 move에서 1을 빼준다

7. 주사위 수만큼 이동했을 때 21 이하이면 한 번에 이동한다

   아니면 한 칸씩 이동해준다

8. 주사위 수만큼 이동한 지점에 이미 다른 말이 있으면 continue로 제외해준다

   만일 도착지점이었다면 도착은 여러 개의 말이 있어도 되므로 예외로 둔다

9. dfs를 반복하면서 주사위 수 10개를 다 사용했으면 최대값을 갱신한다

import sys

input = sys.stdin.readline

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

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 for _ in range(4)]
c = [0 for _ in range(33)]

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