Perfect Squares

from collections import deque
import math

class Solution(object):
  def getNeighbors(self,n):
    x = int(math.sqrt(n))
    neighbors  = []
    for i in range(1,x+1):
      neighbors.append(n - (i **2))
    return neighbors

  def numSquares(self, n):   
    ans = 0
    queue = deque([n])
    visited = set([n])
    while queue:
      size = len(queue)
      # print(queue)
      for _ in range(size):
        rest = queue.popleft()
        if rest == 0:
          return ans
        neighbors = self.getNeighbors(rest)
        # queue.extend(neighbors)
        for neighbor in neighbors:
          if neighbor not in visited:
            queue.append(neighbor)
            visited.add(neighbor)

      ans += 1


n = 12
solution = Solution()
result = solution.numSquares(n)  
print(result)