[Level 2 / 깊이 우선 탐색] 타겟 넘버 + 예제 + Swift

타겟 넘버

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

깊이/너비 우선 탐색이란?

1. 깊이 우선 탐색

DFS: Depth First Search

큐를 이용해 구현한다.

스택 또는 재귀함수로 구현한다.

예시) 미로찾기를 할 때 최대한 한 방향으로 쭉 가다가 길이 없으면 다시 가장 가까운 갈림길로 돌아와서 쭉 탐색한다.

2. 너비 우선 탐색

BFS: Breadth First Search

비 우선 탐색은 최대한 넓게 이동한 뒤 이후 밑으로 이동한다.

큐를 이용해 구현한다.

예시) 미로 찾기에서 최단거리를 구해야 하는 경우에 깊이 우선 탐색보다 유리하다. 깊이 우선 탐색에서 나온 경로는 최단 거리가 아닐 수 있지만, 너비 우선 탐색에서 나온 처음의 해답은 곧 최단거리이기 때문이다.

예시) 지구 상의 존재하는 모든 친구 관계를 그래프로 표현한 후 철수와 영희사이에 존재하는 경로를 찾는 경우에 깊이 우선 탐색의 경우, 모든 친구 관계를 다 살펴보는 반면, 너비 우선 탐색의 경우 철수와 가까운 관계부터 탐색한다.

경로 예제

참고사이트를 참고하였다.

1부터 시작해 N개의 노드를 가지는 그래프에서, 1번 노드에서 N번 노드로 가는 모든 경우의 수를 구하시오.

let n = 5
let edges = [(1, 2), (1, 3), (1, 4), (2, 1), (2, 4), (2, 5), (3, 2), (3, 4), (4, 5)]

경로 예제 풀이

1. edge 정보를 담고 있는 edgeDict 딕셔너리를 만든다. edgeDict는 아래와 같은 형태이다.

   var edgeDict: [Int: [Int]] = [:]
   
   for edge in edges {
       if var array = edgeDict[edge.0] {
           array.append(edge.1)
           edgeDict[edge.0] = array
       } else {
           edgeDict[edge.0] = [edge.1]
       }
   }

   edgeDict = [4: [5], 3: [2, 4], 1: [2, 3, 4], 2: [1, 4, 5]]

2. node에서부터 시작해서, 방문한 노드들은 visited에 넣으며 함수를 돌린다.

   func dfs(node: Int, visited: [Int]) {
       guard node != lastNode else {
           result += 1
           return
       }
       guard let neighbors = edgeDict[node] else { return }
       for edge in neighbors {
           guard visited.contains(edge) == false else { continue }
           dfs(node: edge, visited: visited + [edge])
       }
   }

3. dfs 함수를 문제에서 주어진 대로 1에서부터 시작한다.

   dfs(node: 1, visited: [1])

타겟 넘버 풀기

이 문제는 깊이 우선 검색로 풀어야 한다. 인덱스와 숫자의 합으로 깊이 우선 탐색으로 풀어야 겠다.

나의 풀이

idx가 5일 경우 끝이기 때문에 합이 target과 같다면 result에 1을 추가하는 방법으로 풀었다. 위에서의 경로 예제보다 쉽다는 것을 풀면서 느꼈고, dfs라 쫄았었는데 스스로 풀어서 행복했다. 풀이도 나름 괜춘한 듯😆

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

    func dfs(idx: Int, sum: Int) {
        if !(idx < numbers.count) {
            if sum == target { result += 1}
            return
        }
        let num = numbers[idx]
        dfs(idx: idx + 1, sum: sum + numbers[idx])
        dfs(idx: idx + 1, sum: sum - num)
    }
    dfs(idx: 0, sum: 0)

    return result
}

참고사이트 - 깊이 우선 탐색과 너비 우선 탐색

참고사이트 - 깊이 우선 탐색 예제

[그림 출처 : https://namu.wiki/w/BFS]