DFS (개념)

다른 유형에 비해 감이 잘 안잡히는 문제라 개념부터 잡고 갑니다..

1. 뻗어나가는 가지가 무엇인가
2. 각 노드에 해당하는 값은 무엇인가
3. 더이상 가지가 뻗어나가지 않는 종료조건은 무엇인가

DFS는 언제 쓰이는 가?

• 선택지가 계속 분기됨
• 끝까지 가봐야 정답인지 알 수 있음
• 가능한 모든 경우를 세야 함

기본 유형

dfs(index, total)

• index: 지금 몇 번째 노드를 처리중인지
• total: 지금까지 만든 트리

예시 (타겟 넘버)

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

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

이 문제를 DFS로 생각하는 법

start = 0
├─ +1 → 1
│  ├─ +1 → 2
│  │  ├─ +1 → 3
│  │  └─ -1 → 1
│  └─ -1 → 0
│     ├─ +1 → 1
│     └─ -1 → -1
└─ -1 → -1
   ├─ +1 → 0
   │  ├─ +1 → 1
   │  └─ -1 → -1
   └─ -1 → -2
      ├─ +1 → -1
      └─ -1 → -3

“현재 몇 번째 숫자까지 처리했는가?”
“지금까지 합이 얼마인가?”

dfs(index, total)

• index: 지금 몇 번째 숫자를 처리 중인지
• total: 지금까지 만든 합

그리고 다음 숫자에 대해 두 갈래

dfs(index + 1, total + numbers[index])
dfs(index + 1, total - numbers[index])

완성 코드

def solution(numbers, target):
    answer = 0

    def dfs(index, total):
        nonlocal answer

        # 모든 숫자를 다 사용한 경우
        if index == len(numbers):
            if total == target:
                answer += 1
            return

        # (가지치기) 현재 숫자를 더하는 경우 (재귀호출)
        dfs(index + 1, total + numbers[index])

        # (가지치기) 현재 숫자를 빼는 경우 (재귀호출)
        dfs(index + 1, total - numbers[index])

    dfs(0, 0) # 초기 노드
    return answer