[BOJ/백준] 7682 틱택토

문제 링크 : https://www.acmicpc.net/problem/7682

7682번: 틱택토

 

처음에는 그냥 단순하게 모든 경우를 재귀로 구해서 set에 저장 후 set에 있냐 없냐로 검사했다.

당연히 느리다. 다른 분들이 비해서 느려서 다시 풀어봤다.

 

모두 구하지 말고 입력으로 들어온 문자를 검사를 하는 것으로 했다.

게임의 종료 조건은 가로,세로,대각으로 3개의 말이 모이면 된다. 그래서 if문으로 다 해줬다.

그리고 모든 칸이 다 채워졌는데도 위의 조건이 만족 못해도 게임은 끝난다.

이외의 경우는 다 불가능한 경우이다.

 

불가능한 경우는 아래와 같다.

1. x가 승리하려면 x개수=o개수 +1이고 o가 승리하려면 x개수=o개수이다

우선 위 조건을 만족못하면 불가능한 경우이다.

 

2. x도 끝이나고 o도 게임이 끝나는 경우이다.

xo.

xo.

xox

이 경우 x,o 개수도 조건에 맞아서 둘다 승리로 종료 판단되지만 불가능한 경우이다.

 

3. 모든 칸이 다 채워지지 않았는데 게임이 종료되는 경우이다.

입력이 xo.xo.... 처럼 들어오면 어느하나도 승리하지 못한 경우이다.

이 경우도 불가능한 경우이다.

 

from sys import stdin

input = stdin.readline

def solv():
    while True:
        case = input().strip()
        if case == 'end':
            break
        x_count = case.count('X')
        o_count = case.count('O')

        if x_count == o_count+1 or x_count == o_count:
            typ1,typ2 = ('X','O') if x_count == o_count+1 else ('O','X')
            game_result1 = check_game_end(case, typ1)
            game_result2 = check_game_end(case, typ2)

            if game_result2:
                print('invalid')
            elif not game_result1:
                if case.count('.') == 0:
                    print('valid')
                else:
                    print('invalid')
            else:
                print('valid')
        else:
            print('invalid')

def check_game_end(case,typ):
    if case[0] == typ and case[0] == case[1] == case[2]:
        return True
    elif case[0] == typ and case[0] == case[3] == case[6]:
        return True
    elif case[4] == typ and case[1] == case[4] == case[7]:
        return True
    elif case[4] == typ and case[3] == case[4] == case[5]:
        return True
    elif case[8] == typ and case[6] == case[7] == case[8]:
        return True
    elif case[8] == typ and case[2] == case[5] == case[8]:
        return True
    elif case[4] == typ and case[0] == case[4] == case[8]:
        return True
    elif case[4] == typ and case[2] == case[4] == case[6]:
        return True
    else:
        return False

solv()