타겟 넘버

📖 깊이/너비 우선 탐색(DFS/BFS) > 타겟 넘버

📖What I thought

• 처음엔 숫자를 몇 개만 써도 되는 줄 알고 코드 작성이 이상했음
  • 첫 숫자부터 뒷 숫자를 하나는 + 하나는 -해서 계속 큐에 넣어줌
  • 타겟 숫자에 도달하기만하면 카운트 +1 타겟 숫자에 도달 못했으면 ?? 계속 + - 해줘 → 타겟숫자에 도달하면 이후 뒷 숫자 반복문을 안돌았음 (왜냐면 타겟 숫자 도달하지 못했을 때만 뒷 숫자 + - 해서 dq에 넣어줬으니까)
• 근데 모든 숫자를 다 썼어야 하는거지 즉, 결국엔 이프문 조건이 타겟숫자를 만족하냐 안하냐가 아니라 넘버스를 계속 + -해오면서 마지막 숫자까지 + - 해주었을 때(즉, 인덱스가 마지막 인덱스에 도달했을 때)의!!! 값이 타겟 숫자가 되어야 해용

1. BFS로 첫 숫자부터 뒷 숫자를 하나는 + 하나는 -해서 큐에 푸시하고 큐 안에 값 있는 동안 계속 이거 반복해
2. 근데 그냥 숫자만 큐에 넣어주면 이게 모든 숫자를 다 쓴지 몇 개만 쓴지 알 수가 없잖아?)
   • 그러니까 큐에 넣을 때 + -된 값이랑 인덱스(그니까 현재 숫자 몇 개 쓴 지)를 튜플 형태로 넣어줘
3. 인덱스가 마지막 인덱스가 아니라면?? 그냥 뒷 숫자 + - 해줭~~ 마지막 인덱스라면?? 모든 숫자를 다 사용했다는 뜻. 요 때 타겟 넘버가 되면 정답 +1 해주쎄용~~

📖풀이

📎BFS

from collections import deque
 
def solution(numbers, target):
    n, cnt = len(numbers), 0
    dq = deque([(numbers[0], 0), (-numbers[0], 0)])
    
    while dq:
        x, i = dq.popleft()
        
        i += 1
        if i == n:
            if x == target:
                cnt += 1
            continue
        
        dq.extend([(x + numbers[i], i), (x - numbers[i], i)])
    
    return cnt

📖What I learned

1. 문제를 꼼꼼히 읽자 ㅎㅎ ;;

📖관련 지식

📎Deque

📎BFS(Breadth-First Search)