17825-주사위윷놀이

acmicpc.net/problem/17825

1. 인접노드 정보를 갖는 graph 를 만들자

   • 빨간색흐름을 타는 인접노드

   • 방향이 바뀌는 파란색 흐름만 타는 인접노드

2. 노드마다 점수를 갖는 점수 정보 리스트 만들기

3. 네 마리의 말마다 조건에 맞다면 모두를 각각 DFS 로 재귀를 보내주자

dice = list(map(int, input().split()))
chess = [0 for _ in range(4)]

# 빨간 노드
red = [0 for _ in range(33)]
for i in range(33):
    # 들어가면 다음칸으로 가도록
    red[i] = i + 1
# 도착칸에 들어오면 계속 그 칸으로 가도록
red[21] = 21
red[22], red[23], red[24] = 23, 24, 30
red[25], red[26] = 26, 30
red[27], red[28], red[29] = 28, 29, 30
red[30], red[31], red[32] = 31, 32, 20

# 파란 노드
blue = [0 for _ in range(16)]
blue[5], blue[10], blue[15] = 22, 25, 27

# 해당칸의 점수
score = [0 for _ in range(33)]
for i in range(1, 21):
    score[i] = i * 2
score[22], score[23], score[24] = 13, 16, 19
score[25], score[26] = 22, 24
score[27], score[28], score[29] = 28, 27, 26
score[30], score[31], score[32] = 25, 30, 35


def dfs(dice_index, total):
    global max_total
    if dice_index == 10:
        max_total = max(total, max_total)
        return

    # 4 마리 말에 대하여 반복문 # 어차피 4마리라는걸 생각하자, 그리고 중복되는걸 생각하자
    for i in range(4):
        # 현재 재귀에서 필요한 " 값 " 을 불러서 변수 지정하자
        nx, x, move = chess[i], chess[i], dice[dice_index]
        # 이동하려는 녀석이 파란곳에 있다면
        if nx == 5 or nx == 10 or nx == 15:
            nx = blue[nx]
            # 노드를 미리 옮겨줘서 흐름을 타게 만들어야 한다.
            # 노드를 미리 옮겼기 때문에 주사위 가는 수 1 미리 줄여주자
            move -= 1

        # move 번 노드를 따라 가면된다. 중간에 21이 나온다면 스스로인 인접노드로 계속 재정의될뿐
        for _ in range(move):
            nx = red[nx]

        if nx in chess and nx != 21:
            continue

        chess[i] = nx
        dfs(dice_index + 1, total + score[nx])
        chess[i] = x


max_total = 0
dfs(0, 0)
print(max_total)