[프로그래머스] 사라지는 발판(Python)

https://programmers.co.kr/learn/courses/30/lessons/92345

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

minimax 알고리즘 문제였다 옛날에 다른 회사 지원할 때 코딩 테스트에서 승리할 때 최대한 빨리 이기고 질 때 최대한 늦게 지는 문제를 만났었는데 그때도 못 풀었는데 지금도 못 풀었다..

 

일단 완전 탐색 문제고, 모든 경우에서의 값을 구하는 것은 성공했는데, 어떤 사람이 무조건 이기는지에 대해 구현하는 데에 어려움을 겪었다.

나중에 비슷한 문제가 나왔을 때 참고해야겠다

n,m = 0,0
move = [(0,1),(0,-1),(1,0),(-1,0)]
visit = [[0]*5 for _ in range(5)]
def OOB(x,y):
    return x < 0 or x >= n or y < 0 or y >= m

# 결과값이 
def play(board,curx,cury,opx,opy):
    global visit
    if visit[curx][cury]: return 0
    canWin = 0
    for mov in move:
        dx, dy = mov
        nx, ny = curx + dx, cury + dy
        if OOB(nx,ny) or visit[nx][ny] or board[nx][ny] == 0 : continue
        # 방문처리
        visit[curx][cury] = 1
        opResult = play(board,opx,opy,nx,ny)+1
        # 방문처리 끝
        visit[curx][cury] = 0

        # 현재 저장된 값 패배인데 상대가 졌다고 하면 이기는 경우로 저장
        if canWin % 2 == 0 and opResult % 2 == 1 : canWin = opResult
        # 현재 저장된 값 패배인데 상대가 이겼다고 하면 최대한 늦게 지는 횟수 선택
        elif canWin % 2 == 0 and opResult % 2 == 0 : canWin = max(canWin,opResult)
        # 현재 저장된 값 승리인데 상대가 졌다고 하면 최대한 빨리 이기는 횟수 선택
        elif canWin % 2 == 1 and opResult % 2 == 1 : canWin = min(canWin,opResult)
    return canWin

def solution(board, aloc, bloc):
    global n,m
    n, m = len(board), len(board[0])
    return play(board,aloc[0],aloc[1],bloc[0],bloc[1])