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

eroke 2021. 5. 8. 12:03

문제 :

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

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+

programmers.co.kr

예전에 풀어봤던 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