[프로그래머스] 타겟넘버 with 파이썬 : BFS, 재귀함수

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

프로그래머스

 

(1) BFS : 큐를 통해 값을 묶어 전달 

1. while q: q.popleft()

2. if 종료조건

3. else : q.append()

from collections import deque
def solution(numbers, target):
    cnt = 0
    q=deque([[0,0]])
    while q:
        x, idx=q.popleft()
        
        if idx==len(numbers):
            if x==target:
                cnt+=1
        
        else :  # else가 없으면, if idx==len(numbers)에 해당되도 q에 추가하여 잘못됨
            q.append([x+numbers[idx], idx+1]) # q.popleft()할때마다 q.append()하므로 반복문 사용x
            q.append([x-numbers[idx], idx+1])
            
    return cnt

 

 

(2) 재귀함수 : 재귀함수를 통해 값 전달

1. 전달할 파라미터

2. if 종료조건 : return

3. 그렇지 않으면(else :) 재귀함수로 들어가 반복

cnt=0
def recur(numbers, target, tmp, idx):
    global cnt # 전역변수 cnt를 함수내에서 업데이트 하기 위해 global
    if idx==len(numbers):
        if tmp==target:
            cnt+=1
    else : # else대신 if tmp==target: 후에 return으로 recur함수 종료시킬수도 
        recur(numbers, target, tmp+numbers[idx], idx+1)
        recur(numbers, target, tmp-numbers[idx], idx+1)


def solution(numbers, target):
    recur(numbers, target, 0, 0)
    return cnt