[백준] 7682 틱택토 (파이썬 python)

 

 

문제 링크

 

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

7682번: 틱택토

 

 

문제 풀이

 

처음에는 유효하지 않은 경우를 가지치기 하는 방식으로 풀이하려 했지만,

생각보다 예외 케이스가 많았습니다.

이에 따라 유효한 케이스를 먼저 가지치기하는 방식으로 풀이했습니다.

게임판의 상태가 최종 상태일 경우 유효하다고 반환해야 합니다.

최종 상태로 가능한 경우는 이긴 플레이어를 기준으로 총 3가지로 세웠습니다.

1) X가 이긴 경우 : X의 개수가 O의 개수보다 1 많아야 함

2) O가 이긴 경우 : O의 개수와 X의 개수가 같아야 함

3) 이긴 사람이 없을 경우 : 게임판이 꽉 차야함 (X의 개수 5개, O의 개수 4개)

3번 경우를 명확히 생각하지 못해 10%에서 계속 오류가 났었는데,

이긴 사람이 없을 때 단순히 X의 개수가 1개 더 많다고 유효한 것이 아니라

최종 상태일 경우를 판단하는 것이므로 게임판이 꽉 찼을 경우만 유효합니다.

꽉 차지 않았을 경우는 게임이 더 진행될 수 있는 경우이므로 최종 상태가 아닙니다.

이 세 경우만 미리 걸러 valid를 출력해주고, 세 경우가 아닐 경우 invalid를 출력해주면 완료됩니다.

 

 

전체 코드

def find_bingo(str):
    # 가로
    for i in range(0, 9, 3):
        if input_str[i] == str and input_str[i] == input_str[i + 1] == input_str[i + 2]:
            return True

    # 세로
    for i in range(3):
        if str == input_str[i] and input_str[i] == input_str[i + 3] == input_str[i + 6]:
            return True

    # 대각선
    if str == input_str[0] and input_str[0] == input_str[4] == input_str[8]:
        return True

    if str == input_str[2] and input_str[2] == input_str[4] == input_str[6]:
        return True

    return False

while True:
    input_str = str(input().rstrip())
    if input_str == 'end':
        break
    bingo_o, bingo_x = find_bingo('O'), find_bingo('X')
    num_o, num_x = input_str.count('O'), input_str.count('X')
    if bingo_x and not bingo_o and num_x == num_o + 1:
        print("valid")
        continue
    if bingo_o and not bingo_x and num_o == num_x:
        print("valid")
        continue
    if not bingo_o and not bingo_x and num_x == 5 and num_o == 4:
        print("valid")
        continue
    print("invalid")