[알고리즘] 프로그래머스 - 타겟넘버

문제

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

프로그래머스

 

풀이

예전에는 bfs로 풀었던 문제인데 이번엔 dfs로 풀었다. 내가 워낙 bfs만 써서...dfs도 연습할 겸 ㅎ

dfs / bfs 기본문제다!

 

 

코드

dfs

def solution(numbers, target):
    answer = 0
    n = len(numbers)
    
    def dfs(symbol,i,result):
        nonlocal answer
        if symbol == '-':
            result -= numbers[i]
        else:
            result += numbers[i]

        if i == n-1:
            if result == target:
                answer += 1
            return

        dfs('+',i+1,result)
        dfs('-',i+1,result)

    dfs("+",0,0)
    dfs("-",0,0)
        
    return answer

 

bfs (예전에 풀어놨던)

from collections import deque
def solution(numbers, target):
    answer=0

    q=deque()
    cnt=0
    q.append((numbers[0],cnt))
    q.append((numbers[0]*-1,cnt))


    while q:
        num,cnt=q.popleft()

        cnt+=1

        if cnt < len(numbers):
            q.append((num+numbers[cnt],cnt))
            q.append((num-numbers[cnt],cnt))
        else:
            if num == target:
                answer+=1
    return answer