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

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

너비우선탐색(BFS)

BFS와 DFS란? 대표적인 그래프 **탐색** 알고리즘

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

- 깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식

BFS vs DFS 비교

BFS 방식: A - B - C - D - G - H - I - E - F - J 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회함

DFS 방식: A - B - D - E - F - C - G - H - I - J 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순화함

=> 방식에 따라 노드 탐색의 순서가 달라진다!

이제 BFS를 코드로 구현해보기.

각 노드와 연결된 정점의 연결 관계를 노드를 Key로, 연결된 노드들을 Value로 Dictionary로 나타내주기!

아래처럼 dictionary 만들고 각각 넣어줬다.

var bfsDictionary: Dictionary = Dictionary() bfsDictionary["A"] = ["B", "C"] bfsDictionary["B"] = ["A", "D"] bfsDictionary["C"] = ["A", "G", "H", "I"] bfsDictionary["D"] = ["B", "E", "F"] bfsDictionary["E"] = ["D"] bfsDictionary["F"] = ["D"] bfsDictionary["G"] = ["C"] bfsDictionary["H"] = ["C"] bfsDictionary["I"] = ["C", "J"] bfsDictionary["J"] = ["I"]

이제 탐색을 해야한다.

탐색할 때에는 큐(queue)를 사용한다.

자료구조 중에 Queue!!

탐색해야할 노드를 저장할 큐와 이미 탐색한 노드를 저장할 큐 두개가 필요하다.

강의 따라서 이렇게 구현했다.

func bfs(graph: [String:[String]], startNode: String) -> [String]{ var visited: [String] = [] var needVisit: [String] = [] needVisit.append(startNode) while !needVisit.isEmpty { // get first let node: String = needVisit.removeFirst() if !visited.contains(node) { visited.append(node) needVisit.append(contentsOf: graph[node]!) } } return visited }

위에서 만든 딕셔너리랑 탐색 시작 노드를 "A"로 테스트 돌리면

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

결과 이렇게 나온다..!

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

어렵다ㅠㅠㅠㅠ

어렵다 어려워..

방법 이해하는게 오래걸렸다.

막상 코드 보면 심플..^^

강의 인증샷!!

https://bit.ly/37BpXiC

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

from http://tnqtnq.tistory.com/102 by ccl(A) rewrite - 2021-09-30 15:00:47