leet code - 59. Spiral Matrix II (medium, matrix)

leet code - 59. Spiral Matrix II (medium, matrix)

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.

 

Example 1:

 

Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]

Example 2:

Input: n = 1
Output: [[1]]

 

Constraints:

• 1 <= n <= 20

 

n이라는 숫자가 주어지면 n*n 크기의 매트릭스를 생성해

나선 순회를 하면서 해당 순서의 숫자로 update

 

    def generateMatrix(self, n: int) -> List[List[int]]:
        
        x, y, dx, dy = 0, 0, 1, 0
        res = [[0] * n for _ in range(n)]

        for i in range(n * n):
            res[y][x] = i + 1

            if not 0 <= x + dx < n or not 0 <= y + dy < n or res[y+dy][x+dx] != 0:
                dx, dy = -dy, dx

            x += dx
            y += dy

        return res

 

0, 0 부터 시작. 벡터의 방향은 1, 0 이다.

for 문으로 n*n 만큼 순회하면서 dx dy 를 조절한다.

매트릭스의 끝이나, 이미 방문한 노드 등 경계값의 끝에 이르는 경우 벡터를 90도씩 이동한다.

시계 방향의 전환. 아래쪽 방향에서 왼쪽으로 바뀔때 음의 전환, (-dy) 위쪽에서 다시 오른쪾으로 바뀔때 양의 전환이 일어난다(-dy)