프로그래머스 Lv. 2 Swift 알고리즘 - 타겟 넘버

지금까지 여러 알고리즘을 풀면서 분명 DFS 혹은 BFS 개념을 활용하는 문제를 만났었을 것이다...

하지만 이렇게 명확하게 DFS/BFS 개념으로 접근해서 문제를 풀어본적은 없었다.

DFS만 정확히 이해하고 있으면 풀 수 있는 문제이다.

 

개념은 유명하신 소들이님 블로그를 참고하여 숙지하였다.

트리의 형태로 +와 - 의 가능한 경우를 반영하여 뻗어나가고 더이상 자식 노드가 없는 레벨까지 도달했을때의 값을 찾으면 된다.

(참고한 블로그: https://babbab2.tistory.com/107)

 

 

이 문제를 풀면서 생각한 논리적 흐름

1. 트리의 마지막 노드 부분(number.count)과 인덱스가 같아질 당시의 누적된 sum값이 target 값과 같다면
2. ans에 1을 추가해주는 DFS함수를 만든다.
3. 만약 idx == numbers.count가 성립하지 않는다면 DFS에 idx를 1추가하여 다시 실행시킨다.
4. 이렇게 idx가 누적되면 결국 nubmers.count에 도달하게 되고 도달한 레벨의 영역에 존재하는 case들이 몇개인지 확인할 수 있다.

 

 

* 코드

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    var ans = 0

    func DFS(idx: Int, sum: Int) {
        if idx == numbers.count {
            if sum == target {
                ans += 1
            }
            return
        }
        DFS(idx: idx+1, sum: sum + numbers[idx])
        DFS(idx: idx+1, sum: sum - numbers[idx])
    }

    DFS(idx: 0, sum: 0)

    return ans
}

 

 

정리(Today I Learned)

1. DFS와 BFS는 많이 들었지만 실제로는 처음 구현해봤다. 트리는 주로 인접리스트 방식으로 구현된다. 상황에 따라 노드의 끝까지 내려가며 탐색하는 DFS와 가까운 수평구조로 탐색하는 BFS를 적절히 활용해야겠다.