[코테준비] 11. 백준- 주사위 윷놀이 (17825) python "삼성 SW 역량 테스트 기출 문제"

주사위 윷놀이

• 링크:https://www.acmicpc.net/problem/17825
• 난이도:골드 2
• 분류: 구현, 시뮬레이션, 브루트포스 알고리즘, 백트레킹
• 직접 푼 여부: X -블로그를 보면서 이해하는데 꽤 걸렸다. 

풀이 노트

참고한 블로그1: https://velog.io/@yoonuk/%EB%B0%B1%EC%A4%80-17825-%EC%A3%BC%EC%82%AC%EC%9C%84-%EC%9C%B7%EB%86%80%EC%9D%B4-Python

참고한 블로그2: https://juhi.tistory.com/52

1번을 보며, 이해가 안돼서 열심히 그림판에 그려봤다. 근데 뭔가 너무 지저분 해지고 이해가 안돼서 블로그2를 보니 이해가 되어 그것을 바탕으로 주석을 달았고, 아래 그림을 그렸다. 

 

우선 이 윷놀이 문제를 풀기위해서는 판을 어떻게 나타낼지가 중요하다. 그래서 각 칸의 번호를 부여(빨간색 숫자)하여 각 칸에서 바로 다음에 갈 수 있는 칸을 graph로 표현하고, 각 칸의 점수를 score로 표현하였다. 그리고 코드를 주석과 함께 보면 이해가 될 것이다. 핵심은 저 파란칸에서 "바로"출발할 때는 파란색 화살표 방향으로 가야하므로, "바로"출발할 때, 즉 for문이 돌아갈 때 처음에 그 파란칸(갈 수 있는 곳이 2개)인지 아닌지 확인해야한다. 그래서 len으로 파악. 

빨간색 숫자가 코드에서 graph와 score의 index값이다. 즉, 각 위치의 번호를 의미한다.

 

정답 코드 💻

# 주사위 윷놀이
# ckarh: https://velog.io/@yoonuk/%EB%B0%B1%EC%A4%80-17825-%EC%A3%BC%EC%82%AC%EC%9C%84-%EC%9C%B7%EB%86%80%EC%9D%B4-Python


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

# 준비
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]] # index: 현재칸, value: 현재칸에서 갈 수 있는 칸

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] # index: 칸, value: 점수

def backtracking(depth, result, horse):
    global answer
    if depth ==10: #10번 움직임
        answer = max(answer, result)
        return
    for i in range(4) #말이 총 4개니까
        # 현재 말의 위치 x
        x = horse[i]
        if len(graph[x]) ==2:
            # 파란길로 갈 수 있는 곳이면 (10,20,30)
            x=graph[x][1] #파란색 길로감
        else:
            #아니면 빨간길로 그냥
            x=graph[x][0]

        # 나온 주사위 값 만큼 이동 - 위에서 1 이동했으니 1 덜 이동.
        for _ in range(1, dice[depth]):
            x= graph[x][0]

        # 목적지에 도착 / 아직 목적지 no & 거기 말이 없다면 계속 진행. 아니면 다른말 사용
        if x ==32 or (x<32 and x not in horse):
            before = horse[i]
            horse[i] = x # 현재 말 위치 업데이트
            backtracking(depth+1, result+score[x], horse)
            horse[i] = before # 다른 방법해봐야하니까 원래것으로 다시 변경

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