LeetCode [1275]: Find Winner on a Tic Tac Toe Game

📌 LeetCode [1275]: Find Winner on a Tic Tac Toe Game

🔗 문제 링크

---

문제 설명 📄

3x3 크기의 Tic Tac Toe 보드에서 moves가 주어집니다.
게임에서 승자가 결정되거나 모든 칸이 채워질 때까지의 과정을 시뮬레이션합니다.

• "A"와 "B"가 번갈아가며 이동하며, "A"가 먼저 시작합니다.
• 승자가 발생하면 "A" 또는 "B"를 반환합니다.
• 모든 칸이 채워졌는데 승자가 없으면 "Draw"를 반환합니다.
• 아직 칸이 남아있으면 "Pending"을 반환합니다.

---

문제 접근 방식 📋

1. 보드 생성 및 이동 처리:
   • 3x3 보드를 생성하여 "X"와 "O"로 표시합니다.
   • moves를 순차적으로 처리하며 보드에 이동을 기록합니다.
2. 승리 여부 확인:
   • 각 칸에서 DFS를 사용하여 3개의 동일한 마크가 연속으로 있는지 확인합니다.
   • 방향은 총 8가지 (가로, 세로, 대각선).
3. 결과 판별:
   • DFS 결과로 승자가 나오면 바로 반환.
   • 모든 칸이 채워졌다면 "Draw", 그렇지 않으면 "Pending"을 반환합니다.

---

Solution 💻

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        pattern = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, -1], [-1, 1], [-1, -1], [1, 1]]
        turn = True
        graph = [["" for _ in range(3)] for _ in range(3)]

        for move in moves:
            if turn:
                graph[move[0]][move[1]] = "X"
            else:
                graph[move[0]][move[1]] = "O"
            turn = not turn

        def dfs(x, y, target):
            for px, py in pattern:
                dx, dy = x + px, y + py
                if 0 <= dx < 3 and 0 <= dy < 3 and graph[dx][dy] == target:
                    dx, dy = dx + px, dy + py
                    if 0 <= dx < 3 and 0 <= dy < 3 and graph[dx][dy] == target:
                        if target == "X":
                            return "A"
                        return "B"
            return ""

        for i in range(3):
            for j in range(3):
                if graph[i][j] in ("X", "O"):
                    result = dfs(i, j, graph[i][j])
                    if result != "":
                        return result

        if len(moves) == 9:
            return "Draw"
        else:
            return "Pending"

시간 복잡도 분석 ⏲️

• DFS: 각 칸에서 8방향으로 탐색 (상수 시간).
• 전체 칸 확인: 3x3 보드이므로 총 9번.
• 최종 시간 복잡도: ( O(1) ) (상수 시간).

공간 복잡도 분석 🗄️

• 보드 공간: ( O(3 \times 3) = O(1) ) (상수 공간).
• 기타 변수 공간: ( O(1) ).

---

리팩토링 🛠️

개선된 코드

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        rows, cols = [0] * 3, [0] * 3
        diag, anti_diag = 0, 0
        turn = 1

        for x, y in moves:
            rows[x] += turn
            cols[y] += turn
            if x == y:
                diag += turn
            if x + y == 2:
                anti_diag += turn

            if abs(rows[x]) == 3 or abs(cols[y]) == 3 or abs(diag) == 3 or abs(anti_diag) == 3:
                return "A" if turn == 1 else "B"

            turn *= -1

        return "Draw" if len(moves) == 9 else "Pending"

리팩토링 후 시간 복잡도 ⏲️

• 탐색: 각 이동을 한 번 처리 (( O(1) )).
• 총 시간 복잡도: ( O(n) ), ( n )은 이동 수 (최대 9).

리팩토링 후 공간 복잡도 🗄️

• 보드 사용 대신 카운터로 관리: ( O(1) ).

---