출처: 프로그래머스 코딩 테스트 연습, [프로그래머스] 사라지는 발판
풀이
알고리즘 문제해결전략 책에서 게임이론에 대해 공부했던 적이 있는데 그때 거의 모르는 상태로 그냥 넘어갔는데 이번에 나와 다시 책을 펼치게 되었다. 현재 플레이어가 이기고 지고에 대한 내용은 있었지만 몇번째 턴에서 이기고 지는지에 대한 정보는 없어 조금 응용해서 구현해보았다.
먼저 처음 플레이어 위치에서 게임이 흘려가는 것을 상상하는 것은 너무 많은 경우의 수가 있어 매우 힘들었다. 그래서 게임이 어느정도 진행되고 난 후 플레이어들이 이동할 수 있는 경로에 대해 생각했다. play() 메서드가 0을 반환할 때는 더 이상 움직일 수 있는 발판이 없을 경우이므로 현재 자신의 차례에 지는 것을 의미한다. 그러므로 자연스럽게 짝수를 반환할 때는 자신이 지는 짝수번째에 지는 것을 의미한다. 반대로 홀수를 반환할 때는 자신이 홀수번째에 이기는 것을 의미한다. 그러면 현재 플레이어가 갈 수 있는 발판이 있는데 각 발판을 갔을 경우 게임이 몇번째 차례에 끝나는지 반환한다. 문제에서 이기는 사람은 최선을 다해서 이기려고 하고 지는 사람은 최선을 다해서 버텨야 하므로 갈 수 있는 발판을 갔을 경우 여러 짝수가 반환됐을 경우는 최대한으로 버텨야 하므로 여러 짝수 중 최대값을 저장한다. 또한 짝수 이외 홀수가 반환됐을 경우는 이길 수 있는 경우가 있다는 것을 의미하고 또 최선을 다해서 이겨야 하므로 여러 홀수 중 최소한의 홀수를 저장한다. 만약 홀수가 단 하나도 반환되지 않았을 경우는 짝수중 최고 큰 짝수를 반환하고 홀수가 단 하나라도 반환되었다면 반환된 홀수중 젤 작은 홀수를 반환한다.
1. play() 메서드는 보드와 누구의 턴인지와 각 플레이어의 현재 위치를 파라미터로 받는다.
2. 현재 누구의 턴인지에 따라 이번 턴에 움직일 위치를 선택한다.
3. 만약 현재 위치가 0일 경우(상대가 움직여 현재 발판이 0이 됐을 경우) 자신이 지는 것이기 때문에 바로 0을 반환한다.
4. 현재 발판을 0으로 초기화하고 현재 발판에서 갈 수 있는 발판을 확인한다.
5. count 에 1 + play() 을 하는 이유는 현재 턴을 사용했기 때문에 턴을 1 증가시킨 것이다.
6. 이기는 경우는 최소한으로 지는 경우는 최대한으로 초기화한다.
7. 현재 보드를 1로 다시 초기화해놓는다.
8. 홀수가 있을 경우 홀수를 반환하고 그 다음은 짝수 그리고 홀수, 짝수 모두 초기화가 되어있지 않으면 현재 발판에서 갈 수 있는 발판이 없다는 뜻이므로 0을 반환한다.
만약 play()가 짝수를 반환하게 되면 현재 자신의 차례까지는 진행됐지만 상대편일 때 게임이 종료된 것이고 홀수일 경우는 내 차례일 때 지는 것을 의미한다.
코드
def solution(board, aloc, bloc):
n, m = len(board), len(board[0])
INF = 987654321
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
def play(board, turn, aloc, bloc):
loc = aloc if turn == 0 else bloc
if board[loc[0]][loc[1]] == 0:
return 0
odd, even = INF, -1
board[loc[0]][loc[1]] = 0
for x, y in zip(dx, dy):
next = loc[0] + x, loc[1] + y
if 0 <= next[0] < n and 0 <= next[1] < m and board[next[0]][next[1]] == 1:
if turn == 0:
count = 1 + play(board, turn + 1, next, bloc)
else:
count = 1 + play(board, turn - 1, aloc, next)
if count % 2 == 0:
even = max(even, count)
else:
odd = min(odd, count)
board[loc[0]][loc[1]] = 1
if odd != INF:
return odd
if even != -1:
return even
return 0
return play(board, 0, aloc, bloc)느낀점
DP로 만들어줘야 할 줄 알고 틀린 코드라도 제출해봤는데 맞았습니다라고 나와 소름이 돋았다. 보드판의 크기가 작아서 따로 메모이제이션을 해주지 않아도 되나보다. 너무 오랫동안 이 문제를 붙잡고 있었지만 풀고 났을 때 그 기분은 최근 느껴본 기분 중 최고였다.
