23.05.18 혼자서 하는 틱택토

https://school.programmers.co.kr/learn/courses/30/lessons/160585

프로그래머스

문제 설명:

주어진 틱택토 판을 보고, 다음의 틱택토 규칙대로 진행되었을 때 나올 수 있는 경우인지 아닌지를 판단해야한다.

1. O가 먼저둔다. (O,X,O,X,...)
2. 가로/세로/대각선 1줄(3개)를 완성시키면 해당 인원이 승리하고 게임이 종료된다(더이상 진행되지 않음).

 

시도 1:

먼저 순서를 잘 지켰는지를 확인한다. 순서를 잘 지켰다면 반드시 O가 X 보다 1개 많거나, 같아야한다.

def solution(board):
    count_o=0
    count_x=0
    for row in board:
        for i in row:
            if i=='O':
                count_o+=1
            elif i=='X':
                count_x+=1
    if not (count_x-1<count_o and count_o<count_x+2):
        return 0

순서를 잘 지켰다면, 다음으로는 게임이 이미 승리한 상태인지를 확인한다.

    def victory(board):
        vic=["O"*3,"X"*3]
        # row
        for v in vic:
            if v in board:
                return v[0]
        # col
        trancepose=[''.join(x) for x in list(zip(*board))]
        for v in vic:
            if v in trancepose:
                return v[0]
        # diagonal
        if board[0][0]==board[1][1] and board[1][1]==board[2][2]:
            return board[1][1]
        if board[2][0]==board[1][1] and board[1][1]==board[0][2]:
            return board[1][1]
        return False
    
    ...
    if victory(board)=="O" and (count_x>=count_o):
        return 0
    if victory(board)=="X" and (count_x!=count_o):
        return 0

보드 상태로부터 승리 유무 여부를 판단하는 함수 victory를 만들고, (O가 X보다 먼저 두므로 동시에 승리한 경우는 O의 승리로 간주하고 진행) O가 승리했을 시, 반드시 O가 X 보다 갯수가 많아야하고, 반대의 경우 반드시 갯수가 같아야한다는 것을 이용해 판별하려고했다.

 

그러나 이 방법은 실패하였다. 방법을 찾기위해 반례를 찾던 중 다음의 반례를 찾을 수 있었다.

XXX
OOX
OOO

위 예시를 위 코드에 대입할 경우, O가 승리한 경우이고 X갯수가 O보다 1개적으므로 1이 나온다. 실제로는 O가 이긴 후 1~2턴씩 더 진행된 경우거나, X가 이긴 후 1 턴 씩 더 진행된 경우이므로 성립되지 않는다. 전자를 가정하고 접근하는 경우 다른 O승리, O 갯수 5개 인 존재가능한 케이스와 분별이 불가능하다.

XOX
XOX
OOO

따라서 위 코드로는 이 반례를 해결할 수 없었다.

 

해결: O 승리과 X 승리 따로 체크하기

def victory(player,board):
    v=player*3
    if v in board:
        return True
    trancepose=[''.join(x) for x in list(zip(*board))]
    if v in trancepose:
        return True
    if board[0][0]==board[1][1] and board[1][1]==board[2][2]:
        return True if board[1][1]==player else False
    if board[2][0]==board[1][1] and board[1][1]==board[0][2]:
        return True if board[1][1]==player else False
    return False

...
    if victory("O",board) and (count_x>=count_o):
        return 0
    if victory("X",board) and (count_x!=count_o):
        return 0
    
    return 1

위와같이 O 승리와 X승리를 분리하여 둘 다 체크하면, 위와같은 반례도 해결할 수 있었다.