2022 카카오 코딩테스트 lv.3 사라지는 발판 파이썬

dir = ((-1,0),(0,1),(1,0),(0,-1))

def A_turn(ar,ac,br,bc,cnt,board):
    if board[ar][ac] == 0:
        return (1,cnt)
    winner = []
    loser = []
    flag = False
    for dr,dc in dir:
        nr,nc = ar+dr,ac+dc
        if 0<=nr<len(board) and 0<=nc<len(board[0]) and board[nr][nc] == 1:
            flag = True
            temp = [row[:] for row in board]
            temp[ar][ac] = 0
            iswin,turn = B_turn(br,bc,nr,nc,cnt+1,temp)
            if iswin:
                winner.append(turn)
            else:
                loser.append(turn)
    if flag:
        if winner:
            return (0,min(winner))
        else:
            return (1,max(loser))
    else:
        return (1,cnt)


def B_turn(br,bc,ar,ac,cnt,board):
    if board[br][bc] == 0:
        return (1,cnt)
    winner = []
    loser = []
    flag = False
    for dr,dc in dir:
        nr,nc = br+dr,bc+dc
        if 0<=nr<len(board) and 0<=nc<len(board[0]) and board[nr][nc] == 1:
            flag = True
            temp = [row[:] for row in board]
            temp[br][bc] = 0
            iswin,turn = A_turn(ar,ac,nr,nc,cnt+1,temp)
            if iswin:
                winner.append(turn)
            else:
                loser.append(turn)
    if flag:
        if winner:
            return (0,min(winner))
        else:
            return (1,max(loser))
    else:
        return (1,cnt)


def solution(board, aloc, bloc):
    ar,ac,br,bc = aloc[0],aloc[1],bloc[0],bloc[1]
    answer = A_turn(ar,ac,br,bc,0,board)[1]
    return answer

미니맥스트리란 1:1 게임에서 쓰일 수 있는 알고리즘이다. 나와 상대방은 항상 최선을 다하기 때문에, 실수하지 않고 매번 최선의 방법만 택한다. 따라서 내가 고른 최선은 상대방에겐 최악이 되고 상대방이 고른 최선은 나에겐 최악이 된다.

이 문제에서는 이기는 사람은 최단경로로 이기려 하고, 지는 사람은 최대경로로 지려고 한다.

따라서 재귀를 돌때 만약 이길 수 있다면, 최단경로를 리턴해주고 만약 진다면 최대경로를 리턴해준다.