[백준 7682 / Python] 틱택토

틱택토

🔍 알고리즘 분류

• dfs
• 백트래킹
• 완탐

💡 문제 풀이

1. dfs/백트래킹으로 가능한 말의 조합 모두 생성
   • turn을 인자로 줘서 홀수면 X, 짝수면 O로 놓기
   • turn이 10이면 더 이상 놓을 수 없으므로 종료
   • 한 말로 3칸 연결되면 (2) 종료
2. 3칸 연결 확인
   • 가로 확인
   • 전치 행렬로 변환해서 세로 확인
   • 두 대각선 확인
3. set에 가능한 모든 조합 저장 후 입력 받을 때마다 set에 있는지 확인

📄 코드

• Python

# 한 말이 3칸 이어지는지
def check_line(c):
    # 가로 체크
    for row in board:
        if row.count(c) == 3:
            return True
    transform_board = [list(row) for row in zip(*board)]
    transform_board = tuple(map(tuple, transform_board))
    # 세로 체크
    for row in transform_board:
        if row.count(c) == 3:
            return True
    # 대각선 체크
    for i, j in zip(range(3), range(3)):
        if board[i][j] != c:
            break
    else:
        return True
    # 반대쪽 대각선 체크
    for i, j in zip(range(3), range(2, -1, -1)):
        if board[i][j] != c:
            break
    else:
        return True

# 가능한 모든 경우 탐색
def dfs(turn):
    # 3칸 연결 체크
    if check_line('O') or check_line('X'):
        forms.add(tuple(map(tuple, board)))
        return
    # 꽉 채웠는지 체크
    if turn == 10:
        forms.add(tuple(map(tuple, board)))
        return
    for i in range(3):
        for j in range(3):
            if board[i][j] == '.':
                board[i][j] = 'X' if turn % 2 == 1 else 'O' # 턴이 홀수일 땐 X, 짝수일 땐 O
                dfs(turn + 1)
                board[i][j] = '.'

board = [['.'] * 3 for _ in range(3)]
forms = set() # 2차원 배열을 튜플로 변환 필요

dfs(1) # 첫 번째 턴부터 진행

while True:
    s = input()
    if s == "end":
        break
    
    # 3*3 튜플 격자판 생성
    arr = []
    for i in range(0, 8, 3):
        arr.append(list(s[i:i+3]))
    arr = tuple(map(tuple, arr))

    # 가능한 조합에 없으면 invalid, 있으면 valid
    if arr not in forms:
        print("invalid")
    else:
        print("valid")

• 시간복잡도: O(9!)