[Python] 프로그래머스 타겟 넘버 | 너비 우선 탐색(BFS)

https://school.programmers.co.kr/learn/courses/30/lessons/43165

[타겟 넘버]

level 2

프로그래머스

 

 

---

 

from collections import deque
def solution(numbers, target):
    que = deque()
    que.append((1, numbers[0]))
    que.append((1, -numbers[0]))
    result = 0

    while que:
        q = que.popleft()
        if q[0] == len(numbers):
            if q[1] == target:
                result += 1
        else:
            que.append((q[0]+1, q[1] + numbers[q[0]]))
            que.append((q[0]+1, q[1] - numbers[q[0]]))

    return result


print(solution([4,1,2,1], 4))

 

값을 더하고 빼는 경우만 생각하면 되므로 이진트리 형식으로 생각하면 쉽게 이해할 수 있다.

이진트리의 각 레벨이 numbers의 인덱스 번호가 되고, 해당 numbers[level] 값을 더할지 뺄지의 경우가 나눠진다.

 

BFS의 핵심인 queue에 각 경우에 대해서 tuple형태로 (level, 현재까지 값)을 연속하여 삽입한다.

queue에서 꺼낸 q 는 당연히 본인의 level과 값을 가지고 있을 것이다.

 

앞서 말했듯 level과 numbers의 인덱스는 같다.

이는 numbers[level]의 값을 더할 것인지 뺄것인지로 연산을 분리하여 수행할 수 있도록 한다.

 

결국 우리는 모든 numbers의 값을 사용했을 때 target의 값과 같은지가 궁금하므로

tree의 leaf node일 때, 다시 말해서 level이 numbers의 길이와 같아질 때 값이 target과 같은지만 확인하면 된다.