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

[알고리즘] 패스트캠퍼스 챌린지 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 = Dictionary() 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

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

from http://tnqtnq.tistory.com/103 by ccl(A) rewrite - 2021-10-01 18:26:27