[파이썬 | BOJ | 17825] 주사위 윷놀이

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

17825번: 주사위 윷놀이

문제

주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다.

• 처음에는 시작 칸에 말 4개가 있다.
• 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다.
• 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.
• 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
• 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.

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

입력

첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

풀이

말이 이동하는 기본 뼈대가 되는 경로는 가장 길게 아웃코스로 도는 경로이다.

그런데 그 경로중에서 10, 20, 30을 만나게 되면 지름길로 가게 된다.

각각의 지름길은 또 25에서 최종적으로 합쳐지게 된다.

 

따라서 기본경로를 BRANCH[0], 지름길을 BRANCH[1:4], 합쳐진 최종 지름길을 BRANCH[4]로 표현할 수 있다.

 

그리고 4개의 말을 10번에 걸쳐서 모두 탐색해야 하므로, 총 4^10 = 2^20 = 1024 * 1024로 충분히 브루트 포스로 할만한 크기이다.

 

4개의 말들의 위치정보를 담는 리스트를 준비해서, 각각의 말마다 미리 주어진 주사위 값만큼 전진하는 브루트 포스 과정을 거친다.

 

이때 말들의 위치정보는 (경로, 경로에서의 index)로 저장하고, 어떤 경로에서 다른 경로로 이동하게 되는 모든 경우의수를 따져서 갱신해주면 된다.

 

이 문제에서 주의해야 할 점은 어떤 말을 이동해서 다른 말이 있는곳에 도착하게 되는 경우는 없어야 한다. 그런데 경로를 분리해서 모든 칸은 하나의 (경로, 경로에서의 index)로 표현할 수 있지만 유일하게 (0번 경로, 20번 index)와 (4번 경로, 4번 index)는 같은 40번 칸을 가리키게 되므로 말이 겹치는 것을 확인할때 주의해야 한다.

 

또한 한번에 도착지에 도착하게되면 아무런 점수를 얻지 않음을 유의해야 한다.

 

# [파이썬 | BOJ | 17825] 주사위 윷놀이
import sys
read = sys.stdin.readline
maxAns = sys.maxsize * -1
BRANCH = [[], [], [], [], []]                                                           #20  21
BRANCH[0] = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 0]        
BRANCH[1] = [10, 13, 16, 19]                                                 
BRANCH[2] = [20, 22, 24]
BRANCH[3] = [30, 28, 27, 26]
BRANCH[4] = [25, 30, 35, 40, 0]
 
def solve(cnt, depth):
    global maxAns
    #print(locInfo, cnt, depth)
    if depth == len(diceNum):
        if maxAns < cnt:
            maxAns = cnt
            #print(locInfo, cnt)
        return
 
    for horseNum, li in enumerate(locInfo):
        #현재 위치
        branch, location = li
        
        #이미 도착한 상태면 해당 말을 고를 수 없다.
        if (branch, location) == (0, 21) or (branch, location) == (4, 4): 
            continue
        
        #주사위 정보를 통한 다음위치
        nextLocation = location + diceNum[depth]
 
        #윷말 이동 정리 알고리즘
        #지금 0번 위치에 있는데, 말의 다음 위치가 분기점 이라면,
        if branch == 0:
            #지금 0번 위치에 있는데 말이 종점에 도착한다. (점수를 안준다.)
            if nextLocation >= 22:
                #더이상 말이 이동못할것임
                nextLocation = 21
                nextBranch = branch
            #다음 위치가 10번이라면
            elif BRANCH[branch][nextLocation] == 10:
                #1번 가지로 빠지고, 거기서 0번 위치로 이동함
                nextBranch = 1
                nextLocation = 0
            #다음 위치가 20번 이라면
            elif BRANCH[branch][nextLocation] == 20:
                #2번 가지로 빠지고, 거기서 0번 위치로 이동
                nextBranch = 2
                nextLocation = 0
            #다음 위치가 30번이라면
            elif BRANCH[branch][nextLocation] == 30:
                #3번 가지로 빠지고, 거기서 0번 위치로 이동
                nextBranch = 3
                nextLocation = 0
            #종점도, 분기점도 아니라면
            else:
                #가지는 그대로
                nextBranch = branch
        #지금 1번 위치에 있는데, 
        elif branch == 1:
            #말이 25번을 넘어간다면
            if nextLocation >= 4:
                nextBranch = 4
                nextLocation = nextLocation - 4
            #안넘어 간다면
            else:
                nextBranch = branch
            
 
        elif branch == 2:
            if nextLocation >= 3:
                nextBranch = 4
                nextLocation = nextLocation - 3
            else:
                nextBranch = branch
            
 
        elif branch == 3:
            if nextLocation >= 4:
                nextBranch = 4
                nextLocation = nextLocation - 4
            else:
                nextBranch = branch
            
        #지금 4번 위치에 있는데
        elif branch == 4:
            if nextLocation >= 4:
                #print(locInfo, cnt)
                nextBranch = branch
                nextLocation = 4
            else:
                nextBranch = branch
 
        
        if (nextBranch, nextLocation) == (0, 21) or (nextBranch, nextLocation) == (4, 4):
            locInfo[horseNum] = (nextBranch, nextLocation)
            solve(cnt + BRANCH[nextBranch][nextLocation], depth+1)
            locInfo[horseNum] = (branch, location)
            continue
 
        if (nextBranch, nextLocation) in locInfo:
            continue
        
        if (nextBranch, nextLocation) == (0, 20) and (4, 3) in locInfo:
            continue
        
        if (nextBranch, nextLocation) == (4, 3) and (0, 20) in locInfo:
            continue
 
        locInfo[horseNum] = (nextBranch, nextLocation)
        solve(cnt + BRANCH[nextBranch][nextLocation], depth+1)
        locInfo[horseNum] = (branch, location)
 
diceNum = list(map(int, read().split()))
locInfo = [(0,0), (0,0), (0,0), (0,0)]
solve(0, 0)
print(maxAns)