[알고리즘] 패스트캠퍼스 챌린지 26일차

깊이우선탐색(DFS)

• 너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식
• 깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식

 

비교

• BFS 방식: A - B - C - D - G - H - I - E - F - J
  • 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회함
• DFS 방식: A - B - D - E - F - C - G - H - I - J
  • 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순화함

 

어제 봤던 내용과 자료지만 비교를 위해 한번더!!

 

DFS도 코드로 구현해보기.

우선 BFS와 동일하게 각 노드마다 인접 노드에 대한 정보를 딕셔너리로 저장한다.

요렇게!

var dfsDictionary: Dictionary<String, [String]> = Dictionary<String, [String]>()

dfsDictionary["A"] = ["B", "C"]
dfsDictionary["B"] = ["A", "D"]
dfsDictionary["C"] = ["A", "G", "H", "I"]
dfsDictionary["D"] = ["B", "E", "F"]
dfsDictionary["E"] = ["D"]
dfsDictionary["F"] = ["D"]
dfsDictionary["G"] = ["C"]
dfsDictionary["H"] = ["C"]
dfsDictionary["I"] = ["C", "J"]
dfsDictionary["J"] = ["I"]

 

BFS처럼 이미 방문한 노드를 저장할 큐와 방문할 노드를 저장할 스택 두개를 사용한다.

func dfs(graph: [String:[String]], startNode: String) -> [String] {
    // queue
    var visited: [String] = []
    // stack
    var needVisit: [String] = []
    
    needVisit.append(startNode)
    
    while !needVisit.isEmpty {
        let node: String = needVisit.removeLast()
        if !visited.contains(node) {
            visited.append(node)
            needVisit.append(contentsOf: graph[node] ?? [])
        }
    }
    
    return visited
}

 

테스트도 완료!!

"A" 부터 탐색한 결과는 위에 이론에서 예상했던 결과대로 나온다.

["A", "C", "I", "J", "H", "G", "B", "D", "F", "E"]

 

• 일반적인 DFS 시간 복잡도
  • 노드 수: V
  • 간선 수: E
    • 위 코드에서 while need_visit 은 V + E 번 만큼 수행함
  • 시간 복잡도: O(V + E)

인증샷! ㅎㅎㅎ

 

어제 들었던 BFS 어려웠지만 덕분에 DFS는 금방 잘 이해했다.

BFS는 두개의 큐를 사용하고, DFS는 스택 1개 큐 1개를 사용한다는 점의 차이?

 

 

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.