문제

BOJ 17825: 주사위 윷놀이 https://www.acmicpc.net/problem/17825

풀이

조건

• 처음에는 시작 칸에 말 4개가 있다.
• 화살표의 방향대로만 이동할 수 있다.
• 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다.
• 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다.
• 게임은 10개의 턴으로 이루어진다.
• 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴린다.
• 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.
• 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다.
  • 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
• 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.

풀이 순서

• 윷놀이 판의 위치별로 이동할 수 있는 다음 칸의 위치를 저장한다.
  • 리스트 graph
• 윷놀이 판의 위치별로 얻을 수 있는 점수를 저장한다.
  • 리스트 score
• 백트래킹을 이용해 어떤 말을 이동시킬 지 조합한 경우를 사용해 말을 이동시킨다.
• 말들의 위치를 저장한 배열을 이용해 새로 이동한 위치에 다른 말이 있는지 체크하며 이동한다.

코드

Python

graph = [[1], [2], [3], [4], [5],
         [6, 21], [7], [8], [9], [10],
         [11, 25], [12], [13], [14], [15],
         [16, 27], [17], [18], [19], [20],
         [32], [22], [23], [24], [30],
         [26], [24], [28], [29], [24],
         [31], [20], [32]]

score = [0, 2, 4, 6, 8,
         10, 12, 14, 16, 18,
         20, 22, 24, 26, 28,
         30, 32, 34, 36, 38,
         40, 13, 16, 19, 25,
         22, 24, 28, 27, 26,
         30, 35, 0]

dice = list(map(int, input().split()))
answer = 0


def backtracking(depth, result, horses):
    global answer
    if depth == 10:
        answer = max(answer, result)
        return

    for i in range(4):
        # 현재 말 위치
        x = horses[i]

        # 현재 말 위치가 2갈래 갈 수 있는 위치(10, 20, 30)인지 체크
        if len(graph[x]) == 2:
            # 파란 길 한 칸 진입
            x = graph[x][1]
        else:
            # 빨간 길 한 칸 진입
            x = graph[x][0]

        # 나온 주사위 값 만큼 말 이동(위에서 1칸 이동했기 때문에 1 덜 이동함)
        for _ in range(1, dice[depth]):
            x = graph[x][0]

        # 목적지에 도착했거나 or (아직 목적지가 아니고 and 거기에 말이 없다면)
        if x == 32 or (x < 32 and x not in horses):
            before = horses[i]  # 이전 말의 위치
            horses[i] = x  # 현재 말 위치 갱신

            backtracking(depth + 1, result + score[x], horses)

            horses[i] = before


backtracking(0, 0, [0, 0, 0, 0])
print(answer)

정리

• 윷높이 판의 위치마다 이동할 수 있는 칸을 그래프로 하드코딩하는 방법을 써서 해결했다.
• 처음에는 케이스를 나눠 이동시키려고 했는데 하드코딩한 그래프를 사용하니 편했다.