[DFS,BFS/Programmers] : 타겟 넘버

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

---

DFS

• 구조

• 재귀함수 형태로 구현하기 때문에 무한루프에 빠지지 않게 하는 것이 핵심!

def solution(numbers,target):
    answer=0
    
    def dfs(idx, value):
        if idx==len(numbers):
            if value==target:
                nonlocal answer
                answer+=1
            return
        else:
            dfs(idx+1, value+numbers[idx])
            dfs(idx+1, value-numbers[idx])
    dfs(0,0)
    
    return answer

---

nonlocal

• nonlocal 변수 : 중첩 함수 안에서 활용

  def outer():
      y = 10  

      def inner():
          nonlocal y
          y = 20  # 바깥 함수의 y 수정

      inner()
      print(y)

  outer()  #  20

---

추가 방식

• 도무지 BFS로 푸는 방법이 떠오르지 않아서 .. 거꾸로 공부를 해봅니다..

• BFS
  

  from collections import deque
  def solution(numbers, target):
     answer = 0
     q = deque()
     q.append([numbers[0],0]) # index도 같이 줘서 마지막인지 확인
     q.append([-1*numbers[0],0])
     while q:
         num, idx = q.popleft()
         idx += 1
         if idx < len(numbers):
             q.append([num+numbers[idx], idx])
             q.append([num-numbers[idx], idx])
         else:
             if num == target:
                 answer += 1
     return answer