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

주사위 윷놀이

 문제

 

주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다.

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

주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구해보자.

입력

첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

예제 입력 1 복사

1 2 3 4 1 2 3 4 1 2

예제 출력 1 복사

190

예제 입력 2 복사

1 1 1 1 1 1 1 1 1 1

예제 출력 2 복사

133

예제 입력 3 복사

5 1 2 3 4 5 5 3 2 4

예제 출력 3 복사

214

예제 입력 4 복사

5 5 5 5 5 5 5 5 5 5

예제 출력 4 복사

130

 

 

 풀이

난이도는 골드2로 GRAPH와 SCOPE 설계가 까다로운 문제이다.

https://juhi.tistory.com/52

[Python] 백준 17825: 주사위 윷놀이

설계는 이곳에 참고를하여 구현을 해보았다.

 

고려해야할 것은 완전 탐색을 통해 10개의 dice의 모든 경우의 수를 계산해 주는 것이다. 시간 복잡도를 고려 해보았을때 dice의 수가 10개 밖에 없기 때문에 충분히 가능하다. 그리고 조건 중 가장 중요하게 생각해야 할 것은

• 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
• 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 

 

파란색에서 출발할 경우와, 빨간색에서 출발할 경우를 달리해주고 또한 말이 있는 칸은 이동을 못하도록 하는 조건을 고려해주어야 한다.

 

 

 코드

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

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


# index가 32 일때 마지막 도착이다.
def dfs(cnt_sum, cnt, value):
    global answer
    
    if cnt >= 10:
        answer = max(answer, cnt_sum)
        return

    for i in range(4):
        cnt_idx = value[i] # 현재의 인덱스
        
        if len(graph[cnt_idx]) >= 2: # 현재의 인덱스가 파란색 칸인 경우
            cnt_idx = graph[cnt_idx][1]
        else:
            cnt_idx = graph[cnt_idx][0]
        
        for j in range(1, dice[cnt]): # Dice만큼 이동 한다.
            cnt_idx = graph[cnt_idx][0]
            
        # 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
        if cnt_idx == 32 or (cnt_idx < 32 and cnt_idx not in value):
            before = value[i]
            value[i] = cnt_idx
            dfs(cnt_sum + score[cnt_idx], cnt + 1, value)
            value[i] = before
            
dfs(0,0, [0,0,0,0])
print(answer)