15. 타겟 넘버 ★(DFS)

유형 : DFS

풀이 시간 : 인터넷 참고

 

from collections import deque
def solution(numbers, target):
    #dfs 구현 
    answer = 0
    stack = deque()
    ln = len(numbers)
    
    #첫 번째 원소를 insert하고 시작 
    stack.append([numbers[0], 0])
    stack.append([-numbers[0], 0])
    while stack:
        [curracc, curridx] = stack.pop()
        if curridx == ln-1:
            if target == curracc:
                answer += 1
        else:
            stack.append([curracc + numbers[curridx+1], curridx+1])
            stack.append([-(curracc + numbers[curridx+1]), curridx+1])
    return answer

 

DFS는 stack을 이용하며, while stack: 으로 시작

stack을 pop한 뒤 해당 stack의 자식 노드들을 stack에 추가

(만약 circular 연결이 있다면 이미 방문한 노드는 제외)