[BOJ] 7682. 틱택토 (🥇, 구현)

🔗

풀이

틱택토 게임에서 발생할 수 있는 최종 상태인지를 판별하시오.

이게 왜 백트래킹 분류에...???

아무튼 게임이 종료된 상태냐 진행중이냐를 묻는 것이다. 종료된 상태라고 하면 둘 중 하나가 이겼거나, 더 둘 곳이 없거나 둘 중 하나일것이다. X가 먼저 놓고 O가 다음에 놓는다고 했으므로, X가 이기려면 항상 O보다 1개 더 많은 상태일 것이다. 반대로 O가 이기려면 둘의 개수가 같아야 한다. 그렇다면 다 놓았을 때의 상태는? X는 5개 O는 4개면 된다. 단 이때, 둘 중 한 명도 이긴 상태면 안 된다.

OXOXOXOXX

OXO
XOX
OXX

정확하게는 O가 이긴 상태면 안 된다. 9칸이 다 찼다면 X가 O보다 1만큼만 더 많을 것이므로.

def win(s, board):
    if board[0] == board[4] == board[8] == s:
        return True
    if board[2] == board[4] == board[6] == s:
        return True
    for i in (0, 3, 6):
        if board[i] == board[i+1] == board[i+2] == s:
            return True
    for j in range(3):
        if board[j] == board[j+3] == board[j+6] == s:
            return True
    return False

def game(board):
    x_count = board.count('X')
    o_count = board.count('O')

    x_wins = win('X', board)
    o_wins = win('O', board)

    if x_count == o_count+1 and x_wins and not o_wins:
        return True
    if x_count == o_count and not x_wins and o_wins:
        return True
    if not x_wins and not o_wins and x_count == 5 and o_count == 4:
        return True
    return False

while True:
    board = input()
    if board == 'end':
        break
    if game(board):
        print('valid')
    else:
        print('invalid')