[BOJ] 백준 7682 틱택토 python

백준 Online Judge 문제

7682번: 틱택토

체크리스트

✅ 해결 🟩 미해결 🟩 포기
풀이에 걸린 시간: 약 1시간

---

• 풀이가 떠오른 과정

  ✅ 문제를 읽고 주어진 시간제한과 메모리제한 내에서의 풀이가 떠올랐다.
  🟩 문제를 읽고 시간제한과 메모리제한 내에서 해결이 가능한 지는 모르겠지만 풀이가 떠올랐다.
  🟩 문제를 읽고 풀이가 떠오르지 않았다.
  🟩 문제가 곧바로 이해되지 않았다.

---

• 풀이 작성 과정

  🟩 풀이를 아무런 도움 없이 작성하였다.
  🟩 풀이를 관련된 알고리즘 지식만을 찾아 숙지한 채 작성하였다.
  🟩 풀이를 남의 정답코드를 찾아 참고하여 작성하였다.
  ✅ 알고리즘 개념에 대한 공부를 하다 해당 개념에 대한 문제를 찾았고, 풀었다.

알고리즘 개념

• 깊이 우선 탐색(Depth First Search, DFS)
  깊이 우선 탐색이란 그래프 순회의 방법 중 하나로, 루트노드부터 시작하여 한 방향에 대해 그 리프노드까지 탐색하고, 그 다음 방향을 탐색하는 식으로 그래프를 완전탐색하는 순회방법이다.
  깊이우선탐색이 완전탐색방법과 구분지어지는 부분은 백트래킹을 통한 가지치기로 시간복잡도를 줄일 수 있다는 것인데, 백트래킹이란 탐색 중 더 높은 레벨의 노드까지 도착하기 이전에 일정 자식노드에 대하여 해당 탐색의 내용이 불필요하다는 것을 확인하면 더 이상 탐색을 진행하지 않고 다음 레벨의 다른 자식 노드를 향해 탐색을 진행하는 기법을 뜻한다.

풀이과정

• 일반적으로 테스트케이스의 개수를 첫 번째로 입력해주는데, 이 문제는 테스트케이스의 개수를 입력으로 주지 않기 때문에 while True문을 통해 eoi인 'end'가 입력될 때까지 케이스를 입력받아 함수를 실행시키는 형태로 구현하였다.

• 게임판에 존재하는 임의의 X를 첫 번째 플레이어의 수로 간주하여 번갈아 말을 놓으며 변화하는 게임판의 상태를 자식 노드에 저장한다는 형태의 트리를 DFS로 탐색하는 형태이다. 따라서 플레이어가 말을 놓을 때마다 promising으로 누군가가 승리해서 게임이 종료되지 않는지를 확인하는 형태로 구현하였다.

• 처음에는 게임판의 마지막 형태라는 말을 제대로 숙지하지 못하고 추가로 말을 더 놓을 수 있는 상태여도 형성 가능한 게임판의 형태라면 valid를 출력하게 구현하여 이 부분을 수정해서 구현하였다.

• 이 문제를 메모이제이션을 통해 풀 수 있지 않을까 생각해보았다. 일단 3*3 크기의 게임판 위에서 발생할 수 있는 (가능성을 고려하지 않은) 모든 경우의 수는 3의 9제곱인 19,683개이다. 충분히 완전탐색 가능한 크기이며, 따라서 모든 경우의 수에 대하여 valid한 상태인가 invalid한 상태인가를 확인하여 저장해놓고 input으로 들어오는 게임판의 상태에 따라서 출력하는 형태도 통과가 가능해보인다. 충분히 구현 가능하고 오히려 테스트케이스가 많아질수록 작동시간이 줄어들 것이라고 생각한다.

코드

import sys; rl = sys.stdin.readline
input = ''

board = [0 for _ in range(9)] #0은 비어있음, 1은 'X', 2는 'O'
flag = 0

#플레이어가 말을 놓았을 때마다 그 자리에 놓음으로서 게임이 종료되는지를 확인하기 위한 함수
win = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7]]
def gameover():
    for case in win:
        if board[case[0]-1] != 0 and board[case[1]-1] != 0 and board[case[2]-1] != 0:
            if board[case[0]-1] == board[case[1]-1] == board[case[2]-1]:
                return True
    return False

#dfs를 통해 직접 입력된 게임판의 상태까지 모든 경우의 게임을 진행시키며 promising함수로 가능성을 검토해,
#입력된 게임판의 상태까지 도달하기 이전에 게임이 종료되는 경우 가지치기해줌.
#만약 입력된 게임판의 상태까지 도달하였으나 추가로 말을 놓을 수 있는 경우도 invalid를 반환함.
def tictactoe(string,num,cnt_piece):
    global flag
    if num == cnt_piece:
        if gameover() or cnt_piece==9:
            flag = 1
            return
        else:
            flag = 0
            return
    if gameover():
        return
    for i in range(9):
        if string[i] == 'X' and num%2 == 0 and board[i] == 0:
            board[i] = 1
            tictactoe(string,num+1,cnt_piece)
            if flag == 1: return 'valid'
            board[i] = 0
        elif string[i] == 'O' and num%2 == 1 and board[i] == 0:
            board[i] = 2
            tictactoe(string,num+1,cnt_piece)
            if flag == 1: return 'valid'
            board[i] = 0
    return 'invalid'
        
def sol(string):
    cntO, cntX = 0, 0
    for i in string:
        if i == 'O': cntO+=1
        elif i == 'X': cntX+=1
    #1차적으로 해당 게임판의 상태가 가능한 형태인가를 각 말의 개수에 따라 확인함.
    if cntO<=cntX<=cntO+1 and 0<=cntO<=4 and 0<=cntX<=5:
        return tictactoe(string,0,cntO+cntX)
    else:
        return 'invalid'
    
while 1:
    input = rl().rstrip()
    board = [0 for _ in range(9)]
    if input == 'end':
        break
    flag = 0
    print(sol(input))