Problem :

https://leetcode.com/problems/perfect-squares/


My Solution :

class Solution:
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
if n == int(n**0.5)**2:
return 1
squares = []
for a in range(1, int(n**0.5)+1):
squares.append(a**2)
level = 0
queue = {n}
while True:
level += 1
level_queue = set()
for num in queue:
for a in squares:
if a == num:
return level
if a > num:
break
level_queue.add(num - a)
queue = level_queue


Comment :

BFS를 하면서 최초로 square를 만났을 때 level을 리턴하는 전략을 취해보았다.