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

 

🔗 [백준] 17825 주사위 윷놀이 

📌오늘의 학습 키워드

• DFS, 백트래킹

✨공부한 내용 본인의 언어로 정리하기

• 백트래킹을 구현하는 데까지는 진행했으나..
• 이 엄청나게 큰 윷놀이판을 어떻게 코드로 나타낼 것인가 대해 한참... 고민하다가
• 유투브 선생님의 도움을 받았다...

 

• 갈림길을 해결하는 방법
  • look up table을 적을 때, 갈림길에서 가야하는 길을 추가로 적어준다. 
  • 그리고 말을 움직일 때 한칸을 먼저 움직이는 데 [-1] 인덱스로 접근해서 갈림길인 경우 규칙에 따라 움직이게 해준다.
• 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
  • 말들의 현재 위치를 저장하는 array를 둔다.
  • 만약 말을 이동한 위치가 array 안에 있으면 이동하지 않는다.
  • 말을 이동한 위치가 도착지점이거나 array 안에 없으면 이동한다.

📚오늘의 회고

• • look-up table을 그냥 일단 구현해 놓는게 방법일 때도 있다..!!
  • 일단 무서운 사진으로 사람을 놀래키는 구나
  • 뭔가 조건이 2~3개만 더 달려도 문제가 많이 어려워지는 구나
  • 삼성 기출이구나

[🤓문제 해결 코드]

adj = [[1],[2],[3],[4],[5],[6,21],[7],[8],[9],[10],[11,27],[12],[13],[14],[15],[16,29],[17],[18],[19],[20],[32],[22],[23],[24],[25],[26],[20],[28],[24],[30],[31],[24],[32],[32],[32],[32],[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,  30,  35,  22,  24,  28,  27,  26,  0]


def dfs(count, sum_score):
    global answer
    if count == 10:
        answer = max(answer, sum_score)
        return

    for i in range(4):
        start = current_loc[i]
        piece_loc = adj[start][-1] # 갈림길인 경우 먼저 한칸 이동
        for _ in range(1, dices[count]):
            piece_loc = adj[piece_loc][0]

        # 도착지점이거나 말이 겹치지 않은 경우 이동 - 이게 어려웠음
        if piece_loc == 32 or piece_loc not in current_loc:
            current_loc[i] = piece_loc
            dfs(count + 1, sum_score + score[piece_loc])
            current_loc[i] = start


dices = list(map(int, input().split()))
current_loc = [0, 0, 0, 0]
answer = 0
dfs(0, 0)
print(answer)