나선형 매트릭스

def spiral_order_opt(matrix: list[list[int]]) -> list[int]:
    res = []
    left, right = 0, len(matrix[0])
    top, bottom = 0, len(matrix)
    
    while left < right and top < bottom:
        for i in range(left, right):
            res.append(matrix[top][i])
        top += 1
        for i in range(top, bottom):
            res.append(matrix[i][right - 1])
        right -= 1
        if not (left < right and top < bottom):
            break
        for i in range(right - 1, left - 1, -1):
            res.append(matrix[bottom - 1][i])
        bottom -= 1
        for i in range(bottom - 1, top - 1, -1):
            res.append(matrix[i][left])
        left += 1
    return res

def spiral_order_brute(matrix: list[list[int]]) -> list[int]:
    if not matrix: return []
    rows, cols = len(matrix), len(matrix[0])
    res = []
    visited = set()
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]
    r = c = di = 0
    for _ in range(rows * cols):
        res.append(matrix[r][c])
        visited.add((r, c))
        nr, nc = r + dr[di], c + dc[di]
        if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
            r, c = nr, nc
        else:
            di = (di + 1) % 4
            r, c = r + dr[di], c + dc[di]
    return res