133. [삼성기출29]Python 백준 17825 번 주사위 윷놀이

안녕하세요 코딩하는 덕구입니다.

백준 17825 주사위 윷놀이 입니다.

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

17825번: 주사위 윷놀이

 

백준 17825 주사위 윷놀이 정답코드 입니다. 설명은 아래에 있습니다.

 

order = list(map(int, input().split()))
board = [
    [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] #도착
]
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
         ]

ans = 0
def dfs(piece, depth, res):
    if depth >= 10:
        global ans
        ans = max(ans, res)
        return

    for i in range(4):
        x = piece[i]

        if len(board[x]) == 2:
            x = board[x][1]
        else:
            x = board[x][0]

        for _ in range(1, order[depth]):
            x = board[x][0]

        if (x not in piece) or x == 32:
            before = piece[i]
            piece[i] = x
            dfs(piece, depth + 1, res + score[x])
            piece[i] = before

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

 

문제 접근

1. 말이 이동가능한 윷놀이 판을 구현합니다.

2. 주사위 순서대로 말의 모든 조합을 시도해보면 됩니다.

이때 중복되는 계산을 줄이기 위해 dfs를 사용합니다.

 

 

Python 코드 구현

먼저 윷놀이 판 입니다.

윷놀이 판의 모든 성분은 이동 가능한 다음 index를 갖고있습니다.

도착하게되면 더 이상 움직이면 안되므로 본인의 index를 성분으로 갖습니다.

board = [
    [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] #도착
]

 

 다음은 점수입니다.

윷놀이판의 index에 대응하여 점수를 성분으로 가집니다.

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
         ]

 

 모든 경우의 수를 시도할 dfs입니다.

depth가 10이 넘어가면 점수를 계산하고 종료합니다.

아니라면 4개의 말을 순서대로 선택한 후파란색 위치인지 확인한 후 해당 조건에 맞게 주사위를 굴려 말을 이동시킵니다.이동한곳에 중복되는 말이 없거나, 말이 도착하면 주사위의 다음 순서를 시도합니다.또한 주사위의 현재 순서를 다음 말에 적용하여 이동시킵니다.

def dfs(piece, depth, res):
    if depth >= 10:
        global ans
        ans = max(ans, res)
        return

    for i in range(4):
        x = piece[i]

        if len(board[x]) == 2:
            x = board[x][1]
        else:
            x = board[x][0]

        for _ in range(1, order[depth]):
            x = board[x][0]

        if (x not in piece) or x == 32:
            before = piece[i]
            piece[i] = x
            dfs(piece, depth + 1, res + score[x])
            piece[i] = before

 

함수를 실행시키고, 정답을 출력합니다.

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

 

백준 17825 주사위 윷놀이 Python 코드였습니다.

감사합니다.