[백준/Python] 16571번 : 알파 틱택토

 

문제

 

https://www.acmicpc.net/problem/16571

---

Algorithm

 

min-max 알고리즘의 기본 형태

A와 B가 순서대로 뽑고, 기본 행동 원리는 상대의 이익을 최소화 하기 위해 행동하는 것이다.
예를 들어 숫자 3개가 들어있는 박스가 3개가 있다. [3,5,7] [1,2,4] [5,6,8] 상대 플레이어는 여기서 숫자를 하나씩 뽑아서 새로운 숫자 박스를 만든다. [x1,x2,x3] 그리고 상대는 여기서 뽑은 숫자가 상대의 점수가 된다고 했을 때 그 점수를 최소화 하기 위해서는 가장 작은 숫자들만 남기는 것이다. (min) 그렇게 되면 [3,1,5]가 될 것이고, 이 박스에서 가장 큰 숫자를 고를 것이다.(max)

이것이 간단한 min-max인데 틱택토에서 현재 board의 상태에서 계속 진행했을 때 3가지 경우가 있을 것이다.

1. 모두 지는 경우
2. 한번이라도 비기는 경우
3. 한번이라도 이기는 경우

그럼 현재 플레이어는 이전 턴의 플레이어에게 해당 상태를 넘길 수 있다.

만약 현재 차례가 X이고, board의 상태가 아래와 같다면,

1,2,3,4,5,6 중 한 곳에 둘 것이다.

만약 1,2,3에 둘 경우 패배하고, 4,5,6에 둘 경우 비긴다면, 상대의 이익이 최대가 되는(1,2,3)이 아닌 (4,5,6)에 두게 될 것이다.

만약 6에 두는 경우 X가 이긴다면,

 이전 상태의 board에서 O는 0에 두면 지는 것을 알수 있기 때문에 X에게 0에 둔 상태에 놓인 board를 전달하지 않을 것이다. 그리고 나머지 1,2,3,4,5,6에 대해서도 테스트를 해서 이와 같이 서로 최대한 효율적(내 이익은 최대로, 상대의 이익은 최소로)으로 플레이를 이어갈 것이다.

그렇게 해서 나온 결과를 출력하면 된다.

 

---

 

 

Code

board=[[*map(int,input().split())] for i in range(3)]
firstplayer=1 if sum([i.count(1) for i in board])==sum([i.count(2) for i in board]) else 2

def table_check():
    # 행 체크
    for row in board:
        if row==[1,1,1]:
            return 1
        if row==[2,2,2]:
            return 2
    
    # 열 체크
    for col in range(3):
        if board[0][col]==board[1][col]==board[2][col]==1:
            return 1
        if board[0][col]==board[1][col]==board[2][col]==2:
            return 2
    
    # 대각선 체크
    if board[0][0]==board[1][1]==board[2][2]==1:
        return 1
    if board[0][2]==board[1][1]==board[2][0]==1:
        return 1
    if board[0][0]==board[1][1]==board[2][2]==2:
        return 2
    if board[0][2]==board[1][1]==board[2][0]==2:
        return 2
    return 0

def backtracking(nowplayer):
    end_test=table_check()
    if end_test!=0: return end_test
    otherplayer=2 if nowplayer==1 else 1
    result=[]
    for i in range(3):
        for j in range(3):
            if board[i][j]==0:
                board[i][j]=nowplayer
                result.append(backtracking(otherplayer))
                board[i][j]=0 
    
    if not result:
        return 0
    if nowplayer in result:
        return nowplayer
    if 0 in result:
        return 0
    return otherplayer

answer=backtracking(firstplayer)
if answer==firstplayer:
    print("W")
elif answer==0:
    print("D")
else:
    print("L")