알고리즘 풀이 백준(BOI) 17825) 주사위 윷놀이 (Python)

백준(BOI) 17825 - 주사위 윷놀이

---

 

 

17825번: 주사위 윷놀이

 

[ 문제풀이 ]

 

 주사위를 굴려 나온 숫자만큼 윷놀이 말을 움직여 가면서 발판에 있는 점수들을 더해 얻을 수 있는 점수의 최대값을 출력하는 문제이다. 

 

 

 문제에 대한 이해는 그림으로 보는 게 빠르다.

 

 

 "말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다." 부분에서 해석이 갈릴 여지가 있는데, 말이 움직였을 때 도달하는 발판에 다른 말이 있으면 그냥 그 케이스는 제외하라는 말이다. 

 

 필자는 처음에 윷놀이판을 배열에 구현하려다 엄청나게 애먹었다.

 

 결론부터 말하자면 이 문제는 딕셔너리( 키 : 벨류 로 이루어지는 자료형) 로 만드는 것이 가장 쉽다. 처음에 배열로 이 문제를 풀 때는 몇 번의 시행착오를 겪은 후에야 통과했지만 나중에 딕셔너리로 풀 때에는 아주 쉽게 통과했다.

 

혹시나 도움이 될 수 있기에 이번 포스팅에서는 필자가 풀었던 두 가지 방법 모두를 소개하려 한다. 참고로, 두 가지 방법 모두 DFS로 풀었다.

 

 

 

1. 윷놀이판을 배열로 구현하였을 경우

 필자가 처음에 풀었던 방식으로, 윷놀이판을 2차원 배열에 담았다. 윷놀이판 같은 경우는 크게 외곽으로 쭉 빨간 선을 갈 경우, 맨 처음 파란선을 거쳐가는 경우, 두 번째 파란선을 거쳐 가는 경우, 세 번째 파란선을 거쳐 가는 경우 네 가지로 구분했다.

 

grid = []
grid.append([0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40])
grid.append([0,13,16,19,25,30,35,40])
grid.append([0,22,24,25,30,35,40])
grid.append([0,28,27,26,25,30,35,40])

 

 이후 각 말들의 위치를 저장하기 위해 다음과 같이 선언해준다.

horseState = [(0,0),(0,0),(0,0),(0,0)]

 

 초기 상태에선 어떤 말을 움직여도 결과가 같으므로 첫 번째 말을 DFS에 담아 보내주었다.

def go(horse, count, horseState, result):
"""
.
생략
.
"""


go(0,0,horseState,0)

 

 DFS에 들어오면 먼저 horseState를 깊은복사해준다. 깊은복사의 경우 원본 배열이 바뀌게 되면 완전탐색의 의미가 없어지기 때문이다. deepcopy가 너무 느릴까봐 일일이 복사해줬다.

 이후 매개변수로 넘어온 말을 주사위대로 움직여준다. 윷놀이판을 배열로 구현하였으므로 갈림길(파란부분)에 서게 되면 다른 루트(다른 배열)로 넘겨주는 처리를 해줘야한다. 이는 move() 메소드에 구현하였다.

def move(horseState, dice):
    global grid
    nowx, nowy = horseState
    if nowx == 0:
        nextx = 0
        if nowy == 5: nextx = 1; nowy = 0
        elif nowy == 10 : nextx = 2; nowy = 0
        elif nowy == 15 : nextx = 3; nowy = 0
    else: nextx = nowx
    return nextx, nowy + dice if nowy + dice < len(grid[nextx]) else -1

 nowx 는 grid의 첫번째 인덱스 (즉, 경로들) 을 의미한다. 첫 번째 경로 ( nowx == 0 ) 일 경우 발판의 5, 10, 15번째 인덱스에 위치하면 다른 경로로 이동하게 된다. 배열 범위를 넘어버리는 것은 도착을 의미한다. y값에 -1을 반환해주었다.

 

이후 말의 위치를 저장해놓는 배열을 깊은복사해놓은 copyState에서 위 말의 움직임을 반영해주고, 도착하지 않았을 경우 (즉, 점수가 있는 발판에 도달한 경우) 점수도 반영해준다.

 

    copyState[horse] = (rx, ry)
    if ry != -1: result += grid[rx][ry]
    if count == 9: answer = max(answer, result); return

 카운트가 9가 되었다는 것은 다음 주사위가 존재하지 않는다는 의미다. 때문에 점수만 반영해주고 종료해야한다. 최대값을 구하는 문제이므로 answer에는 항상 최대값만 저장시킨다.

 

 

이후 DFS를 계속 실행하기 위해 go() 메소드를 재귀해야한다. 

 

 

여기서 필자의 경우 윷놀이판을 배열에 구현해서 큰 난관에 부딛혔다. 

 

문제에서 보면 도달하는 발판에 다른 말이 있을경우 해당 케이스는 넘겨야 한다. 

 

이는 적절한 조건을 주어서 for문에서 continue만 잘 주면 해결되는 문제이다. 하지만 구현해놓은 윷놀이판 배열을 다시 보자.

 

grid.append([0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40])
grid.append([0,13,16,19,25,30,35,40])
grid.append([0,22,24,25,30,35,40])
grid.append([0,28,27,26,25,30,35,40])

 

grid의 인덱스는 윷놀이판의 점수(발판)를 의미한다. 즉 인덱스는 현재 위치고 값은 점수이다.

만약, 첫 번째 말이 지름길을 통하지 않고 4-5-5-5-1 를 거치면 40에 도달하게 된다.

그런데, 두 번째 말이 5-5-2를 거치면 어떻게 될까? 첫 번째 지름길을 거쳐 40에 도달하게 된다. 로직대로라면 두 번째 말은 첫 번째 말이 이미 40에 위치하기 때문에 마지막 2를 수행할 수 없다.

 

이같은 경우는 40 뿐만이 아니라 grid의 1~3  (지름길을 타는 경로)의 25, 30, 35, 40 도 마찬가지다. 이 발판에 위치하는 경우 다른 경로에도 말이 있는지 확인해줘야 한다. 딕셔너리로 윷놀이판을 구현할 경우에는 해당 키(발판)만 참조하면 되므로 이런 애로사항이 없다. 

 

아무튼, 재귀는 다음과 같이 구현했다.

 

    for i in range(4):
        oper = True
        if copyState[i][1] == -1: continue
        nx, ny = move(copyState[i], inputList[count+1])
        if ny != -1 and (nx, ny) in copyState: continue
        for ix,iy in copyState:
            if nx == 0 and ny == 20:
                if ((ix == 1 or ix == 3) and iy == 7) or (ix == 2 and iy == 6): oper = False; break
            elif nx == 1:
                if ny == 4:
                    if (ix == 3 and iy == 4) or (ix == 2 and iy == 3): oper = False; break
                elif ny == 5:
                    if (ix == 3 and iy == 5) or (ix == 2 and iy == 4): oper = False; break
                elif ny == 6:
                    if (ix == 3 and iy == 6) or (ix == 2 and iy == 5): oper = False; break 
                elif ny == 7:
                    if (ix == 3 and iy == 7) or (ix == 2 and iy == 6) or (ix == 0 and iy == 20): oper = False; break 
            elif nx == 2:
                if ny == 3:
                    if (ix == 1 or ix == 3) and iy == 4: oper = False; break
                elif ny == 4:
                    if (ix == 1 or ix == 3) and iy == 5: oper = False; break
                elif ny == 5:
                    if (ix == 1 or ix == 3) and iy == 6: oper = False; break
                elif ny == 6:
                    if ((ix == 1 or ix == 3) and iy == 7) or (ix == 0 and iy == 20) : oper = False; break
            elif nx == 3:
                if ny == 4:
                    if (ix == 1 and iy == 4) or (ix == 2 and iy == 3): oper = False; break
                elif ny == 5:
                    if (ix == 1 and iy == 5) or (ix == 2 and iy == 4): oper = False; break
                elif ny == 6:
                    if (ix == 1 and iy == 6) or (ix == 2 and iy == 5): oper = False; break 
                elif ny == 7:
                    if (ix == 1 and iy == 7) or (ix == 2 and iy == 6) or (ix == 0 and iy == 20): oper = False; break                
        
        if oper: go(i, count+1, copyState, result)    

 

2. 윷놀이판을 딕셔너리로 구현하였을 경우

 딕셔너리로 구현할 경우 말을 이동시킬 때 키만 참조하면 되므로 위와 같은 애로사항이 없다. 먼저 인덱스로 말판을 정해주고 각 인덱스에 대한 점수를 윷놀이판을 반영해 구현해주면 된다.

 

gridDict = {
 0:[1,2,3,4,5],
 1:[2,3,4,5,6],
 2:[3,4,5,6,7],
 3:[4,5,6,7,8],
 4:[5,6,7,8,9],
 5:[21,22,23,24,25],
 6:[7,8,9,10,11],
 7:[8,9,10,11,12],
 8:[9,10,11,12,13],
 9:[10,11,12,13,14],
 10:[27,28,24,25,26],
 11:[12,13,14,15,16],
 12:[13,14,15,16,17],
 13:[14,15,16,17,18],
 14:[15,16,17,18,19],
 15:[29,30,31,24,25],
 16:[17,18,19,20,-1],
 17:[18,19,20,-1,-1],
 18:[19,20,-1,-1,-1],
 19:[20,-1,-1,-1,-1],
 20:[-1,-1,-1,-1,-1],
 21:[22,23,24,25,26],
 22:[23,24,25,26,20],
 23:[24,25,26,20,-1],
 24:[25,26,20,-1,-1],
 25:[26,20,-1,-1,-1],
 26:[20,-1,-1,-1,-1],
 27:[28,24,25,26,20],
 28:[24,25,26,20,-1],
 29:[30,31,24,25,26],
 30:[31,24,25,26,20],
 31:[24,25,26,20,-1]
}
scoreDict = {
    -1: 0, 0: 0, 1: 2, 2: 4, 3: 6, 4: 8, 5: 10, 6: 12, 7: 14, 8: 16, 9: 18, 10: 20,
    11: 22, 12:24, 13:26, 14:28, 15:30, 16:32, 17:34, 18:36, 19:38, 20:40, 21: 13, 22: 16,
    23: 19, 24: 25, 25: 30, 26: 35, 27: 22, 28: 24, 29: 28, 30: 27, 31: 26
}

gridDict는 인덱스로 구현한 발판의 위치로, 주사위로 갈 수 있는 다음 발판을 각 각 적어놓은 것이다. -1은 도착이다.

scoreDict는 해당 인덱스에 대한 점수를 적어놓은 것이다. 이를 분리해놓은 이유는 30을 가진 발판이 2개 있 듯, 중복되있는 발판이 있기 때문이다.

 

말의 위치는 state라는 1차원 배열에 저장해준다. 해당 배열에는 위 gridDict의 키값을 저장하는 것이다.

state = [0,0,0,0]

 

딕셔너리로 구현하면 재귀 역시 쉬워진다. 그냥 키만 확인하면 된다.

def go(horse, count, result, state):
    global gridDict, scoreDict, answer, inputArr
    copyState = state.copy()
    nowDice = inputArr[count] - 1
    copyState[horse] = gridDict[copyState[horse]][nowDice]
    nowScore = scoreDict[copyState[horse]]
    
    if count == 9 : answer = max(answer, result + nowScore); return

    nextDice = inputArr[count+1] - 1
    for i in range(4):
        if copyState[i] == -1: continue
        if gridDict[copyState[i]][nextDice] != -1 and gridDict[copyState[i]][nextDice] in copyState: continue
        
        go(i, count+1, result + nowScore, copyState)

---

 

[ 전체 소스코드 ]

 

 - 배열로 구현한 코드

import copy

def move(horseState, dice):
    global grid
    nowx, nowy = horseState
    if nowx == 0:
        nextx = 0
        if nowy == 5: nextx = 1; nowy = 0
        elif nowy == 10 : nextx = 2; nowy = 0
        elif nowy == 15 : nextx = 3; nowy = 0
    else: nextx = nowx
    return nextx, nowy + dice if nowy + dice < len(grid[nextx]) else -1


def go(horse, count, horseState, result):
    global grid, inputList, answer
    # deep copy
    copyState = [(0,0) for _ in range(4)]
    for i in range(4):
        copyState[i] = horseState[i]    
    rx, ry = move(copyState[horse], inputList[count])
    copyState[horse] = (rx, ry)
    if ry != -1: result += grid[rx][ry]
    if count == 9: answer = max(answer, result); return
    
    for i in range(4):
        oper = True
        if copyState[i][1] == -1: continue
        nx, ny = move(copyState[i], inputList[count+1])
        if ny != -1 and (nx, ny) in copyState: continue
        for ix,iy in copyState:
            if nx == 0 and ny == 20:
                if ((ix == 1 or ix == 3) and iy == 7) or (ix == 2 and iy == 6): oper = False; break
            elif nx == 1:
                if ny == 4:
                    if (ix == 3 and iy == 4) or (ix == 2 and iy == 3): oper = False; break
                elif ny == 5:
                    if (ix == 3 and iy == 5) or (ix == 2 and iy == 4): oper = False; break
                elif ny == 6:
                    if (ix == 3 and iy == 6) or (ix == 2 and iy == 5): oper = False; break 
                elif ny == 7:
                    if (ix == 3 and iy == 7) or (ix == 2 and iy == 6) or (ix == 0 and iy == 20): oper = False; break 
            elif nx == 2:
                if ny == 3:
                    if (ix == 1 or ix == 3) and iy == 4: oper = False; break
                elif ny == 4:
                    if (ix == 1 or ix == 3) and iy == 5: oper = False; break
                elif ny == 5:
                    if (ix == 1 or ix == 3) and iy == 6: oper = False; break
                elif ny == 6:
                    if ((ix == 1 or ix == 3) and iy == 7) or (ix == 0 and iy == 20) : oper = False; break
            elif nx == 3:
                if ny == 4:
                    if (ix == 1 and iy == 4) or (ix == 2 and iy == 3): oper = False; break
                elif ny == 5:
                    if (ix == 1 and iy == 5) or (ix == 2 and iy == 4): oper = False; break
                elif ny == 6:
                    if (ix == 1 and iy == 6) or (ix == 2 and iy == 5): oper = False; break 
                elif ny == 7:
                    if (ix == 1 and iy == 7) or (ix == 2 and iy == 6) or (ix == 0 and iy == 20): oper = False; break                
        
        if oper: go(i, count+1, copyState, result)    
            
    

inputList = list(map(int, input().split()))
grid = []; answer = 0
grid.append([0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40])
grid.append([0,13,16,19,25,30,35,40])
grid.append([0,22,24,25,30,35,40])
grid.append([0,28,27,26,25,30,35,40])
horseState = [(0,0),(0,0),(0,0),(0,0)]
go(0,0,horseState,0)
print(answer)

 

 - 딕셔너리로 구현한 코드

def go(horse, count, result, state):
    global gridDict, scoreDict, answer, inputArr
    copyState = state.copy()
    nowDice = inputArr[count] - 1
    copyState[horse] = gridDict[copyState[horse]][nowDice]
    nowScore = scoreDict[copyState[horse]]
    
    if count == 9 : answer = max(answer, result + nowScore); return

    nextDice = inputArr[count+1] - 1
    for i in range(4):
        if copyState[i] == -1: continue
        if gridDict[copyState[i]][nextDice] != -1 and gridDict[copyState[i]][nextDice] in copyState: continue
        
        go(i, count+1, result + nowScore, copyState)
    

inputArr = list(map(int, input().split()))
gridDict = {
 0:[1,2,3,4,5],
 1:[2,3,4,5,6],
 2:[3,4,5,6,7],
 3:[4,5,6,7,8],
 4:[5,6,7,8,9],
 5:[21,22,23,24,25],
 6:[7,8,9,10,11],
 7:[8,9,10,11,12],
 8:[9,10,11,12,13],
 9:[10,11,12,13,14],
 10:[27,28,24,25,26],
 11:[12,13,14,15,16],
 12:[13,14,15,16,17],
 13:[14,15,16,17,18],
 14:[15,16,17,18,19],
 15:[29,30,31,24,25],
 16:[17,18,19,20,-1],
 17:[18,19,20,-1,-1],
 18:[19,20,-1,-1,-1],
 19:[20,-1,-1,-1,-1],
 20:[-1,-1,-1,-1,-1],
 21:[22,23,24,25,26],
 22:[23,24,25,26,20],
 23:[24,25,26,20,-1],
 24:[25,26,20,-1,-1],
 25:[26,20,-1,-1,-1],
 26:[20,-1,-1,-1,-1],
 27:[28,24,25,26,20],
 28:[24,25,26,20,-1],
 29:[30,31,24,25,26],
 30:[31,24,25,26,20],
 31:[24,25,26,20,-1]
}
scoreDict = {
    -1: 0, 0: 0, 1: 2, 2: 4, 3: 6, 4: 8, 5: 10, 6: 12, 7: 14, 8: 16, 9: 18, 10: 20,
    11: 22, 12:24, 13:26, 14:28, 15:30, 16:32, 17:34, 18:36, 19:38, 20:40, 21: 13, 22: 16,
    23: 19, 24: 25, 25: 30, 26: 35, 27: 22, 28: 24, 29: 28, 30: 27, 31: 26
}
answer = 0
state = [0,0,0,0]
go(0,0,0,state)
print(answer)