[백준] 7682번 틱택토

경우의 수를 정말 잘 따져봐야하는 문제

BFS 알고리즘을 이용해서 풀었는데, 경우의 수와 고려해야할 반례가 많아서 구현이나 시뮬레이션 같은 문제였다. 코테에서 정말 만난다면 반례 생각 못하고 그냥 냈을 것 같다ㅎㅎ

먼저 input을 받고 말의 개수를 먼저 센다. 조건에 맞지 않으면 바로 "invalid"를 print하고 종료한다.

1. X의 최대 개수는 5개
2. O의 최대 개수는 4개
3. X와 O의 개수 차이는 0 또는 1이어야 한다. (더 많거나 -이면 종료한다.)

해당 조건을 통과 후, BFS 알고리즘을 통해 가로, 세로, 대각선으로 bingo 된 개수를 센다.
X와 O의 bingo 개수를 bfs() 함수를 통해 리턴받는다.

승자가 2명이거나 0명일 경우, 다음과 같으면 invalid를 출력한다.

1. X, O 모두 승자이다.
2. 게임판이 다 차지 않았는데(.가 존재하는데) 승자가 존재하지 않는다.

마지막으로 따져봐야할 조건은 다음과 같다.

1. X가 승자일 경우(빙고가 1줄, 2줄일 경우) X와 O의 개수차이는 1개여야 valid하다.
2. O가 승자일 경우(빙고가 1줄일 경우만 가능) X와 O의 개수차이는 0개여야 valid하다.
3. 게임판이 다 찼을 경우, 승자가 존재하지 않아도 valid하다.

코드는 아래와 같다.

import sys
from collections import deque
input = sys.stdin.readline

def bfs(x, y, nx, ny):
    q = deque([(x, y, graph[x][y])])
    while q:
        now = q.popleft()
        if (now[0] == 2 and nx == 1) or (now[1] == 2 and ny == 1) or (now[0] == 2 and now[1] == 2):
            return 1
        if 0 <= now[0]+nx < 3 and 0 <= now[1]+ny < 3:
            if graph[now[0]+nx][now[1]+ny] == now[2]:
                q.append((now[0]+nx, now[1]+ny, graph[now[0]+nx][now[1]+ny]))
    return 0

while True:
    game = input().rstrip()
    if game == "end":
        break
    
    graph = []
    for i in range(3):
        inner = [game[x] for x in range(9) if i*3+2 >= x >= i*3]
        graph.append(inner)
    
    # 말의 개수 체크
    x_cnt = game.count('X')
    o_cnt = game.count('O')
    if x_cnt-o_cnt not in [0, 1] or x_cnt > 5 or o_cnt > 4:
        print("invalid")
        continue
    
    is_full = 0
    bingo = [0, 0]
    for i in range(3):
        for j in range(3):
            ans = 0
            if graph[i][j] == '.': # 말이 다 차지 않은 채 종료
                is_full = 1
            
            if j == 0:
                ans += bfs(i, j, 0, 1)
            if i == 0:
                ans += bfs(i, j, 1, 0)
            if i == 0 and j == 0:
                ans += bfs(i, j, 1, 1)
            if i == 2 and j == 0:
                ans += bfs(i, j, -1, 1)
            
            if graph[i][j] == 'X':
                bingo[0] += ans
            elif graph[i][j] == 'O':
                bingo[1] += ans
    
    # 승자가 둘이다, 게임판이 다 안찼는데 승자가 존재하지 않는다.
    if (is_full == 1 and 1 not in bingo) or (bingo[0]>=1 and bingo[1]>=1):
        print("invalid")
        continue
    
    # 이것때메 한참 헤맴.. 여러 개 빙고가 나와도 오케이ㅠㅠ
    if bingo[0] in (1, 2) and x_cnt-o_cnt == 1:
        print("valid")
    elif bingo[1] == 1 and x_cnt-o_cnt == 0:
        print("valid")
    elif bingo[0] == 0 and bingo[1] == 0 and is_full == 0:
        print("valid")
    else:
        print("invalid")