백준 17825번 주사위 윷놀이 (Python)

문제에서 주어진 게임판에서 주사위 윷놀이를 하는 게임입니다.

게임판

• 시작 칸에서 말 4개가 출발합니다.
• 말은 게임판에 그려진 화살표대로 이동할 수 있습니다. 단, 파란색 칸에서 출발하면 파란색 화살표를 타야합니다.
• 말이 도착 칸에 도달하면 주사위에 나온 수와 관계 없이 이동을 마칩니다.
• 게임은 10개의 턴으로 진행됩니다. 매 턴마다 1~5가 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킵니다.
• 말이 이동을 마치는 칸에 다른 말이 있으면 그 말을 고를 수 없습니다.  단, 이동을 마치는 칸이 도착 칸이면 고를 수 있습니다.
• 말이 이동을 마칠 때마다 적혀있는 수가 점수에 추가됩니다.

주사위에서 나오는 수 10개를 미리 알고 있을 때, 구할 수 있는 점수의 최대값을 구하는 문제입니다.

 

 

풀이

0. 변수, 맵 재구성

dices # 미리 알고 있는 주사위
score # 각 칸마다 점수
answer # 최대 점수 값

맵 재구성

출발 지점을 인덱스 0으로 두고 도착 지점의 인덱스를 32로 총 칸의 개수가 33개입니다.

각 칸마다 인덱스를 붙여주었습니다(동그라미 안에 숫자가 인덱스입니다). 가장 바깥쪽의 칸들이 점수가 2씩 증가하는 형태로 이어져있어 우선 바깥쪽에 먼저 인덱스를 붙여주었습니다. 그 다음, 5에서 시작하는 경우, 10에서 시작하는 경우 15에서 시작하는 경우로 차례대로 번호를 매겨준 다음 도착지점까지 인덱스를 붙여주었습니다.

 

1. 칸 이동시 주의할 점

이동 시 주의해야 될 칸들을 살펴보겠습니다. 주사위의 크기는 5이므로 최대 5칸 앞으로 갔을 때, 제가 정해준 칸들의 번호가 뒤바뀌는 경우 주의를 해야합니다.

 

다음과 같은 칸들에서 주의해야 합니다.

• 5번에서 출발하는 경우, 20~22번에서 출발하는 경우
• 10번에서 출발하는 경우, 23~24번에서 출발하는 경우
• 16~19번에서 출발하는 경우

위와 같은 경우 주사위로 인해 인덱스가 1씩 증가하는 형태가 아닌 갑자기 바뀌는 형태가 되므로 위의 조건이 나타나면 현재 위치를 잘 조정해줄 수 있도록 했습니다.

 

2. 인덱스 바뀔 시, 위치 변경 방법

인덱스가 1씩 증가하는 순서가 아닌 갑자기 바뀌는 경우 인덱스를 조정해주도록 하겠습니다.

def getStartPos(pos):
    if pos == 5:
        return 19
    elif pos == 10:
        return 22
    elif pos == 15:
        return 24
    else:
        return pos
...

pos = horse[j]
startPos = getStartPos(pos)
newPos = startPos+dice
if (pos == 5 or 20 <= pos <= 22) and newPos > 22:
    newPos += 5
elif (pos == 10 or 23 <= pos <= 24) and newPos > 24:
    newPos += 3
elif 16 <= pos <= 19 and newPos > 19:
    newPos += 11

if newPos > 32:
    newPos = 32

if newPos != 32 and newPos in horse:
    continue

현재 말의 위치를 pos에 저장하고 시작 지점에 대한 정보를 얻어올 수 있도록 했습니다.

파란색 칸인 5, 10, 15 위치에 있을 때에는 다음 칸의 인덱스가 확 바뀌게 되므로 getStartPos를 통해 각각 19, 22, 24에서 시작하도록 지정해주었습니다. 나머지 칸들은 자신의 위치에서 시작하도록 했습니다.

이 후 각 조건마다 (시작 지점 + 주사위)가 지정된 범위를 넘어갈 경우 게임판에 맞는 위치로 이동할 수 있도록 했습니다.

 

또한, 말이 도착 지점에 도달하면 더 이상 진행되지 않도록 해주었습니다. 그리고 이동하려는 지점에 말이 이미 있다면 이동하지 못하도록 했습니다.

 

3. 최대값 구하기

말의 개수가 4개, 주사위를 10번 던져서 이동을 하게 되므로 모든 경우의 수는 2^20으로 진행을 해도 괜찮은 수준으로 생각하여 dfs로 모든 경우의 수를 구해보도록 했습니다.

 

def dfs(i, total, horse):
    global answer
    if i == 10:
        answer = max(answer, total)
        return

    dice = dices[i]

    for j in range(4):
        pos = horse[j]
        startPos = getStartPos(pos)
        newPos = startPos+dice
        if (pos == 5 or 20 <= pos <= 22) and newPos > 22:
            newPos += 5
        elif (pos == 10 or 23 <= pos <= 24) and newPos > 24:
            newPos += 3
        elif 16 <= pos <= 19 and newPos > 19:
            newPos += 11

        if newPos > 32:
            newPos = 32

        if newPos != 32 and newPos in horse:
            continue

        newTotal = total+score[newPos]
        newHorse = horse[:]
        newHorse[j] = newPos

        dfs(i+1, newTotal, newHorse)

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

i는 현재 턴의 번호,  total은 현재까지 점수, horse는 현재 말들의 위치를 담은 리스트입니다.

10개의 주사위를 모두 확인한 경우 정답과 비교하여 최대값을 구할 수 있도록 했습니다.

 

말이 이동하려는 지점에 다른 말이 없을 경우에 새로운 점수와 새로운 말 위치를 구한 뒤 dfs를 실행해주도록 했습니다.

모든 실행이 끝나고 정답을 출력해주도록 했습니다.

 

 

 

 

 

 

해결

이번 문제는 조금 빠르게 끝내 다행이었던 것 같습니다.

 

17825 주사위 윷놀이

17825번: 주사위 윷놀이