- Problem

2596. Check Knight Tour Configuration

- 내 풀이(BFS)

D = ((-2, 1), (-2, -1), (2, -1), (2, 1), (-1, 2), (-1, -2), (1, -2), (1, 2))

class Solution:
    def checkValidGrid(self, grid: List[List[int]]) -> bool:
        N = len(grid)
        q = deque([(0, 0)])
        moves = 1

        while q:
            y, x = q.popleft()

            for dy, dx in D:
                ny = y + dy
                nx = x + dx

                if 0 <= ny < N and 0 <= nx < N and grid[ny][nx] == grid[y][x] + 1:
                    q.append((ny, nx))
                    moves += 1

        return moves == (N**2)

- 결과

• 시간 복잡도: O(N*N)
• 공간 복잡도: O(N*N)