[파이썬 python] 삼성 기출 백준 17825번 - 주사위 윷놀이

백준 17825번 주사위 윷놀이 문제를 풀어보겠습니다. 

이 문제를 통해 백트래킹과 구현력을 기를 수 있습니다.

 

1. 문제 링크

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

17825번: 주사위 윷놀이

2. 문제 요약

시작칸에 말 4개가 있다.
파란색 칸에서 이동하면 파란색 화살표를 타야한다. 나머지는 빨간색 화살표를 탄다.
도착 칸으로 이동하면 주사위에 나온 수와 관계없이 이동을 마친다.
10개의 턴으로 이루어진다.
1~5까지 한 면에 하나씩 적혀있는 주사위를 굴리고, 주사위에 나온 수만큼 이동시킨다.
말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다.
단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
말이 이동을 마칠 때마다 칸에 적힌 수가 점수에 추가된다.

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

3. 아이디어 정리

생각해볼것

1. 게임판 경로를 어떻게 표현할 것 인가
2. 백트래킹 코드를 어떻게 짤 것 인가

게임판의 칸들을 인덱스로 표현합니다.

이제 테이블을 만들건데, 각 인덱스마다 주사위가 1,2,3,4,5가 나왔을 때 이동할 인덱스를 나타냅니다.

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

 

4. 문제 풀이

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

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

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


def dfs(num, cnt, horse):
    global ans
    if num == 10:
        ans = max(ans,cnt)
        return
   
    for i in range(4):
        x = horse[i]
        horse[i] = board[x][dice[num]]
        if horse.count(horse[i]) == 1 or horse[i]==21:
            dfs(num+1,cnt+number[board[x][dice[num]]],horse)
        horse[i] = x



horse = [0,0,0,0]
ans = 0
dfs(0,0,horse)
print(ans)

 

5. 배울점

 

*백트래킹 에서 생각할 것*

1. global ans => 최대, 최소 나타내기 위해서

2. 종료 조건

3. 원상태로 돌리기 => 재귀안에 연산을 넣어서 가능한 원상태로 돌릴 변수를 줄인다.