프로그래머스 DFS/BFS : 타겟넘버

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

• BFS와 DFS로 해결할 수 있다.

BFS(deque)

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

    answer = 0
    q = deque() # 덱 선언
    n = len(numbers) 
    
    q.append([numbers[0], 0]) # 첫번째 인덱스 삽입
    q.append([-1*numbers[0], 0]) # 첫번째 인덱스 삽입
    
    while q:
        cur, idx = q.popleft()
        idx += 1
        if idx < n : 
            q.append([cur+numbers[idx], idx])
            q.append([cur-numbers[idx], idx])
        else:
            if cur == target:
                answer += 1
    return answer

BFS(stack)

def solution(numbers, target):

    answer = 0
    lst = []
    n = len(numbers) 
    
    lst.append([numbers[-1], n-1]) # 첫번째 수 삽입
    lst.append([-1*numbers[-1], n-1]) # 첫번째 수 삽입
    
    while lst:
        cur, idx = lst.pop()
        idx -= 1
        if idx >= 0 : 
            lst.append([cur+numbers[idx], idx])
            lst.append([cur-numbers[idx], idx])
        else:
            if cur == target:
                answer += 1
    
    return answer

DFS(재귀)

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