[Python3]프로그래머스_사라지는 발판

문제출처: https://school.programmers.co.kr/learn/courses/30/lessons/92345

정리

22년도 카카오 채용 마지막 문제였다.
이전에 체스게임을 만든 적이 있는데 그때 사용한 알고리즘이 "민맥스 알고리즘"이다. 발판게임도 마찬가지로 "민맥스 알고리즘"을 활용하여 푸는 문제였다.
나는 체스게임을 만들면서 많이 공부하고 느꼈던 점도 많았지만 이번 문제를 보면서 비슷한 발상조차 하지 못해서 아직 부족하다는 생각이 들게하는 문제였다.

다른 사람들의 코드를 보면서도 느낀 점이 정말 많고 주석이나 이번 포스트를 쓰면서 많이 정리된 것 같다.

풀이

본 풀이는 먼저 질문게시판의 힌트를 활용하여 구현에 성공한 뒤 다른 사람들의 풀이들을 참고하며 리팩터링하였다.😂

1. 어느 플레이어든 현위치에서 최선의 플레이를 한다. 문제에서는 이기는 판이라면 최소한의 움직임으로 이기고 지는 판이라면 최대의 움직임으로 져야 한다고 설명하지만 이는 "민맥스 알고리즘"을 안다면 유추할 수 있는 힌트지만 매우 헷갈릴 수 있다. 모든 상황에서 이길 수 있는 최선의 수를 생각하는 것이 지는 상황에서도 늦게 질 수 있고 이기는 상황에서는 빠르게 이길 수 있는 것이다.

• 만약 이길 수 있다면 그 중 최솟값을 리턴하는 방향으로 움직인다.
• 질 수 밖에 없다면 그 중 최댓값을 리턴하는 방향으로 움직인다.

2. 결국 어느 플레이어든 질 수 밖에 없는 외통수같은 상황이 생긴다.

• 더이상 움직일 발판이 없는 경우
• 상대방 플레이어가 같은 발판에 있다가 움직인 경우

3. 만약 현재 플레이어가 진다면 상대 플레이어는 이긴다.
   현 플레이어가 외통수로 져야한다면 이동 가능한 움직임은 0이다. (k번째 재귀함수)
   반대로 상대 플레이어는 1칸을 움직여 이길 수 있다. (k-1번째 재귀함수)
   현 플레이어는 2칸을 움직여 질 것이다. (k-2번째 재귀함수)
   ...

• 턴이 번갈아가며 움직이기 때문에 패배하는 플레이어는 짝수의 이동 가능한 움직임을 가지고 승리하는 플레이어는 홀수의 이동 가능한 움직임을 가진다.

4. 현위치에서 움직일 수 있는 칸들에 대하여 승리 또는 패배의 경우의 수를 아래와 같이 정리할 수 있다.

• ret : 패배한 경우의 수 res : 승리한 경우의 수 >> 갱신
• ret : 패배한 경우의 수 res : 패배한 경우의 수 >> 둘 중 큰값
• ret : 승리한 경우의 수 res : 승리한 경우의 수 >> 둘 중 작은값
• ret : 승리 res : 패배 >> 갱신 X

5. 나도 이전까지 DFS를 구현할때 2차원 배열을 새로 생성하여 플레이어들의 이동을 마킹하고 이전 위치를 0으로 만들어 주어진 배열이 재귀함수의 수만큼 새로 할당하여 불필요한 메모리를 많이 사용했는데 전역변수로 방문배열을 할당하여 재귀함수를 호출하기 이전에 현위치를 마킹하고 재귀함수가 끝났을 때 해제하면 효율적인 DFS 구현이 가능하다. 재귀함수의 특성에 대해 조금만 고민해본다면 왜 가능한지 알 것이다.

코드

def solution(board, aloc, bloc):
    n,m = len(board),len(board[0])
    directions = [(1,0),(-1,0),(0,1),(0,-1)]
    
    # Out Of Boundary
    def OOB(x,y):
        return x<0 or x>=n or y<0 or y>=m
    
    # 재귀함수의 방문여부를 체크
    global g_vis
    g_vis = [[0]*m for _ in range(n)]
    
    # 승리할 경우 남은 이동거리는 짝수이고 패배할 경우는 홀수이다.
    def dfs(curx,cury,opx,opy):
        global g_vis
        # 예를들어 플레이어 A와 플레이어 B가 같은 칸에 있을 때 플레이어 A가 이동을 했다면 
        # vis[curx][cury] = 0 -> vis[curx][cury] = 1
        # 즉, 플레이어 B 차례에서 vis[curx][cury] == 1일 경우 패배한다.
        if g_vis[curx][cury]:
            return 0
        
        ret = 0
        for d in directions:
            nx,ny = curx+d[0],cury+d[1]
            if OOB(nx,ny) or board[nx][ny]==0 or g_vis[nx][ny]:
                continue
            
            # 방문
            g_vis[curx][cury] = 1
            
            # 턴이 넘어가면서 다음 (curx,cury)는 현재의 (opx,opy)
            res = dfs(opx,opy,nx,ny)+1
            
            # 방문해제
            g_vis[curx][cury] = 0
            
            # ret : 패배한 경우의 수 res : 승리한 경우의 수 >> 갱신
            if ret%2==0 and res%2==1:
                ret = res
            # ret : 패배한 경우의 수 res : 패배한 경우의 수 >> 둘 중 큰값
            elif ret%2==0 and res%2==0:
                ret = max(res,ret)
            # ret : 승리한 경우의 수 res : 승리한 경우의 수 >>  둘 중 작은값
            elif ret%2==1 and res%2==1:
                ret = min(res,ret)
            # ret : 승리 res : 패배 >> 갱신 X    
    
        return ret
    
    return dfs(aloc[0],aloc[1],bloc[0],bloc[1])