DFS/BFS (Level 2) : 타겟 넘버 (Python)

문제 : 

코딩테스트 연습 - 타겟 넘버

예전에 풀어봤던 dfs/bfs 문제를 다시 풀어보았다

 

 

Solution

예전 풀이 : BFS (deque() 사용)

from collections import deque
def solution(numbers, target):
    answer = 0
    size=len(numbers)
    dq=deque()
    dq.append((0,0))
       
    while dq:
        cur,cnum=dq.popleft()
        
        if cur==size and cnum==target:
            answer+=1
        
        else:
            if cur<size:
                nnum=numbers[cur]
                dq.append((cur+1,cnum+nnum))
                dq.append((cur+1,cnum-nnum))    
    return answer

 

이번 풀이 : DFS

res=0
def dfs(numbers,num,target,idx):
    global res
    if idx==len(numbers):
        if num==target:
            res+=1
            return
        else : return
    
    dfs(numbers,num+numbers[idx],target,idx+1)
    dfs(numbers,num-numbers[idx],target,idx+1)
    
def solution(numbers, target):
    global res
    dfs(numbers, 0, target, 0)
    return res