[BOJ/백준] 16571 알파 틱택토

def checkWin(play):
    play_num = players[play]

    for x in range(3):
        if arr[x][0] == arr[x][1] == arr[x][2] == play_num:
            return 2
    
    for y in range(3):
        if arr[0][y] == arr[1][y] == arr[2][y] == play_num:
            return 2

    if arr[0][0] == arr[1][1] == arr[2][2] == play_num:
        return 2

    if arr[0][2] == arr[1][1] == arr[2][0] == play_num:
        return 2

    return 0 


def dfs(rc,play):
    global result
    if checkWin((play+1)%2)>1:
        return -1
    if rc <remain_cnt:
        check_result = 10
        for idx in range(remain_cnt):
            if not visited[idx]:
                visited[idx] = True
                x,y = remain_list[idx]
                arr[x][y] = players[play]
                check_result = min(check_result,dfs(rc+1,(play+1)%2))
                visited[idx] = False
                arr[x][y] = 0
        if check_result == 10 or check_result == 0:
            return 0
        else:
            return -check_result
    return 0 
arr = []

# 1 = X
# 2 = O
# 착수하는 사람 부터
cnt_1 = 0
cnt_2 = 0
remain_cnt = 0
remain_list = []
players = [1,2]
for x in range(3):
    temp = list(map(int,input().split()))

    for y in range(3):
        if temp[y] == 1:
            cnt_1 += 1
        elif temp[y] == 2:
            cnt_2 += 1
        else:
            remain_cnt += 1
            remain_list.append((x,y))

    arr.append(temp)
visited = [False for _ in range(remain_cnt)]

start = 0
if cnt_1 > cnt_2:
    start = 1




result = dfs(0,start)
answer = ['D','W','L']
print(answer[result])

 이 문제는 어려웠던 문제였다.  이 문제는 각각 최선의 수로 둔다는 것은 해당 수를 두고 다음턴에, 지지 않기를 바라는 상황이다.

 

그래서 상대턴이 시작할때, 이전턴에 뒀던 플레이어의 승리여부를 체크하고 체크를 한뒤에는 음수를 보내준다.

 

왜냐하면 서로 승패는 반대로 되기 때문이다. 그리고 승부가 나지 않았을 시에는 0을 반환하도록 한다.

 

 

 

def check():
    for x in range(3):
        prev_num = arr[x][0]
        if not prev_num:continue
        for y in range(1,3):
            if prev_num != arr[x][y]:
                break
        else:
            return prev_num
    
    for y in range(3):
        prev_num = arr[0][y]
        if not prev_num: continue
        for x in range(1,3):
            if prev_num != arr[x][y]:
                break
        else:
            return prev_num

    prev_num = arr[0][0]
    if prev_num:
        for k in range(1,3):
            if prev_num != arr[k][k]:
                break
        else:
            return prev_num
    
    prev_num = arr[0][2]
    if prev_num:
        for k in range(1,3):
            if prev_num != arr[k][2-k]:
                break
        else:
            return prev_num

    return 0


def dfs(rc,player):
    check_num = check()
    if check_num != 0:
        return check_num

    if rc == 0: return -1
    response = []
    for x in range(3):
        for y in range(3):
            if arr[x][y]:continue
            arr[x][y] = player
            response.append(dfs(rc-1,3-player))
            arr[x][y] = 0
    if player in response:return player
    if -1 not in response: return (3-player)
    return -1

arr = [list(map(int,input().split())) for _ in range(3)]
cnt_1 = 0
cnt_2 = 0
player = 1
r_cnt = 0
for x in range(3):
    for y in range(3):
        if arr[x][y] == 1:
            cnt_1 += 1
        elif arr[x][y] == 2:
            cnt_2 += 1
        else:
            r_cnt += 1


if cnt_1 > cnt_2:
    player = 2


result = dfs(r_cnt,player)

if result == -1:
    print('D')
elif result == player:
    print('W')
else:
    print('L')

이 풀이가 좀 더 직관적일 수 있다.

 

모든 결과들을 저장한뒤에 해당 결과 내에서, 해당 플레이어의 번호가 있으면 승리한 것이므로, 해당 플레이어 번호를 보내주고,

 

무승부인 -1이 없으면 상대방이 이긴거기 때문에 상대방의 플레이어 번호를 return 해준다.

 

그리고 둘다 아닌경우에는 무승부이므로 -1을 반환해준다.

 

이 문제는 최선의 수가 무엇인지, 어떻게 승패를 판단하는지 어려웠던 문제였다.