[프로그래머스] DFS/BFS - 타겟 넘버(파이썬 문제 풀이)

문제 링크

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

단순하게 DFS를 이용해 문제를 풀이했습니다.

상태 트리 각 노드의 레벨이 numbers의 요소를 하나씩 탐색하는 인덱스가 되고 해당 인덱스를 더할 때, 뺄 때 두가지의 경우로 가지를 내려나갑니다.

레벨이 numbers의 길이만큼 도달하면 탐색을 종료하고 지금까지 연산한 값이 target 값이라면 카운팅을 추가합니다!

 

문제 풀이(파이썬)

---

def DFS(L, sum, numbers, target):
    global cnt

    if L>=len(numbers):
        if sum == target:
            cnt += 1
    else:
        DFS(L+1, sum+numbers[L], numbers, target)
        DFS(L+1, sum-numbers[L], numbers, target)


def solution(numbers, target):
    global cnt
    cnt = 0

    DFS(0, 0, numbers, target)
    return cnt