문제

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

참고

https://sujeng97.tistory.com/36?category=999116

풀이과정

이 문제를 어떻게 풀면 좋을지 고민을 많이 했는데, 도저히 떠오르지 않아서 블로그를 참고해서 풀이했다. 핵심 아이디어는 다음과 같다.

이기는 사람은 최단거리로, 지는 사람은 최대거리로 이동한다는 것이다

이를 위해서 아래와 같은 코드 구현이 이뤄졌고, 기본적으로 DFS기반으로 풀이가 진행되었다.

느낀점

1. 같은 함수를 두개로 나누어서 표현한다는 점이 흥미로웠다.
2. 문제의 요구사항을 너무 어렵게 생각하는게 아닐까 생각이 들었다.

Code

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
            board[ar][ac] = 0
            iswin,turn = B_turn(br,bc,nr,nc,cnt+1,board[:])
            board[ar][ac] = 1

            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
            board[br][bc] = 0
            iswin,turn = A_turn(ar,ac,nr,nc,cnt+1,board[:])
            board[br][bc] = 1
            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