[Programmers] 문제 7 – 사라지는 발판[python]

코딩테스트 연습 - 사라지는 발판

게임 이론과 브루트 포스(완전탐색)을 활용해 풀 수 있는 문제입니다.

 

문제의 규칙에 따라, 두 사람은 발판이 없는 곳으로는 이동할 수 없으며, 

더 이상 이동할 수 없는 경우, 이는 해당 사람의 패배했음을 의미합니다.

 

두 사람은 항상 최선의 선택을 따라 이동하며, 이는 다음과 같습니다.

1. 반드시 패배하는 경우, 최대한 게임을 오랫동안 지속할 수 있는 방법을 선택한다.
2. 이길 수 있는 방법이 존재하는 경우, 그 중에서 게임을 가장 빠르게 끝낼 수 있는 방법을 선택한다.

위의 내용을 바탕으로 현재 위치에서 가능한 모든 결과에 따라 할 수 있는 최선의 결과를 선택하면서 재귀함수를

진행해나간다면, 문제를 해결할 수 있습니다.

 

 

def movement(x,y,bx,by,depth):

 

현재의 위치에 대해, 재귀함수 $movement$는 아래 3가지의 상태를 필요로 합니다.

(x,y) : 현재 턴에 이동할 사람의 위치
(bx,by) : 상대의 위치
depth: 자신과 상대가 지금까지 이동한 횟수의 합

if not board[x][y]: #현재 위치에 발판이 없는 경우 패배
    return (0,depth)    #현재까지의 답을 리턴함

또한, 자신을 호출한 함수에게 (현재 플레이어의 승리 가능 여부,최선의 이동 횟수)를 리턴합니다.

만약 현재 위치에 발판이 존재하지 않는다면, 패배를 의미하므로, $movement$는 현재 상태인

(0 : 현재 플레이어가 패배함,depth : 이동횟수는 총 depth회)를 리턴합니다.

 

flg = False #일단 진다로 가정
bestMove = depth

board[x][y] = 0

for i in range(4):
    nx,ny = x + dx[i],y + dy[i]
    if not (0 <= nx < n and 0 <= ny < m) or not board[nx][ny]: continue

    result = movement(bx,by,nx,ny,depth+1)
    flg,bestMove = max((not result[0],[-1,1][result[0]] * result[1]),(flg,bestMove))

board[x][y] = 1
return (flg,abs(bestMove))

flg : 현재 위치에서의 승리 가능여부를 확인하는 boolean
bestMove : 현재 위치에서 취할 수 있는 최적의 이동횟수 (이동 못하는 경우를 위해 depth를 초기값으로 가짐)

 

만약 1개 이상의 승리가 가능한 경우의 수가 존재한다면, flg변수는 참이 되며, 가장 작은 이동 횟수를 취합니다.

반대로 승리가 불가능하다면, flg변수는 거짓이 되며, 가장 큰 이동 횟수를 취합니다.

 

이는 문제에서 언급된 "각 선수는 현재 상황에서 최적의 선택을 한다"를 만족합니다.

 

나의 승리 여부는 상대의 승리 여부를 반전한 값과 같으므로,  not result[0]값이 현재 플레이어의 승리 가능 여부가

됩니다. 이 때, 튜플을 활용해 max((flg.bestMove),(result[0],-result[1] if not flg else result[1]))의 , 보다 간편하게 조건의 구현이 가능합니다,.

 

 

 

전체 소스코드는 다음과 같습니다.

dx,dy = [1,0,-1,0],[0,1,0,-1]

def solution(board, aloc, bloc):
    n,m = len(board),len(board[0])
    #게임이 끝날 때까지 양 플레이가 움직일 수 있는 최대 횟수
    #각 플레이어는 현재 자신의 상황에서 최적으로 이동함
    #이길 수 있는 경우 -> 최단경로 선택
    #어떻게 해도 지는 경우 -> 최장경로 선택

    def movement(x,y,bx,by,depth):

        if not board[x][y]: #현재 위치에 발판이 없는 경우 패배
            return (0,depth)    #현재까지의 답을 리턴함

        flg = False #일단 진다로 가정
        bestMove = 0

        board[x][y] = 0

        for i in range(4):
            nx,ny = x + dx[i],y + dy[i]
            if not (0 <= nx < n and 0 <= ny < m) or not board[nx][ny]: continue

            result = movement(bx,by,nx,ny,depth+1)
            flg,bestMove = max((not result[0],[-1,1][result[0]] * result[1]),(flg,bestMove))

        board[x][y] = 1
        return (flg,abs(bestMove))

    return movement(aloc[0],aloc[1],bloc[0],bloc[1],0)[1]