40. Perfect Squares(bfs)

문제

perfect square는 정수의 제곱인 수이다.

1, 4, 9는 perfect square이고 3, 11은 아니다.

 

정수 n을 인수로 받아 더해서 n이 되는 perfect square의 최소 개수를 구하시오. 

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

 

해결 방식

leetcode 유저 xiey0017

https://leetcode.com/problems/perfect-squares/discuss/71475/Short-Python-solution-using-BFS

루트 노드(n)에서 노드값이 0인 곳 까지 가는 최단거리를 구하는 것처럼 생각할 수 있음.

 

n = 12인 경우를 가정.

1) 큐에 12 삽입.

2) 큐의 요소를 하나 꺼냄.

3) 12보다 작은 perfect square를 구함 (base 1에서 시작)

4) 12 - perfect square가 0이면 최단거리를 찾았다는 뜻 => depth 반환

     12 - perfect square가 0이 아니라면 => queue에 12 - perfect square 삽입

5) base를 1 늘려서 구한 perfect square가 12보다 작을 때까지 3)~5) 과정 반복

      => queue에 11(12 - 1²), 8(12 - 2²), 3(12 - 3²)이 들어감

6) 2)번과정부터 반복

from collections import deque 

def numSqaures(n):
    if n < 2:
        return n

    queue = deque([n])
    depth = 0

    while queue:
        depth += 1
        for _ in range(len(queue)):
            current = queue.popleft()
            base = 1

            while base * base <= current:
                rest = current - base * base

                if rest == 0:
                    return depth 
                else:
                    queue.append(rest)

                base += 1

    return depth