[알고리즘] BFS 구현

개념

너비 우선 탐색으로, Breadth-First-Search, 줄여서 BFS라고 한다.

인접한 노드들을 우선 탐색하는 방식이다.

 

 

위의 이미지에서 숫자가 탐색하는 순서라고 생각하면 된다.

 

탐색 노드부터 인접한 노드들을 탐색하고 -> 모두 탐색하면 그 노드들의 인접한 노드들부터 탐색하는 것이다.

같은 레벨에 있는 (같은 층에 있는) 노드들부터 탐색하는 것이라고 생각하면 된다.

 

🤔 오른쪽? 왼쪽?

참고로 너비 우선 탐색에서 하나의 노드에서 인접 노드들 중 

오른쪽을 먼저 탐색하는지 / 왼쪽을 먼저 탐색하는지 순서는 중요하지 않다.

➡️ 같은 레벨에 존재하기 때문에, 어디를 먼저 탐색하더라도 같은 레벨에 있는 노드를 먼저 탐색해야 다음 레벨(아래)로 이동할 수 있기 때문이다. 

 

구현

0. 그래프 생성 

왼쪽과 같이 그래프가 있을 때 이를 인접 리스트 방식으로 표현하면 오른쪽과 같다.

그리고 이를 코드로 나타내면 아래와 같이 작성할 수 있다.

let graph: [String: [String]] = [
    "A" : ["B", "C"],
    "B" : ["A", "D", "E"],
    "C" : ["A", "F"],
    "D" : ["B"],
    "E" : ["B"],
    "F" : ["C"],
]

 

1. 너비 우선 탐색 

너비 우선 탐색은 보통 두 개의 큐로 표현한다.

✅ 방문 해야 하는 노드를 저장하는 큐 (= needVisitQueue)

✅ 이미 방문한 노드를 저장하는 큐 (= visitedQueue)

 

그리고 아래의 과정을 반복한다.

1. 탐색할 노드의 데이터를 needVisitQueue에 넣는다.
2. needVisitQueue의 첫번째 값을 추출해서(= 큐이므로 FIFO) visitedQueue에 해당 값이 존재하는지 확인한다.
   1. 만약 visitedQueue에 추출한 값이 존재하면, 추출한 값을 버리고
   2. 다음 첫번째 값을 추출해서 다시 확인한다. 
   3. 1-2의 과정을 needVisitQueue가 비워지면 그 때 탐색이 끝나는 것이다.
3. 추출된 값이 존재하지 않으면 visitedQueue에 추가한다. 
4. 추출된 값(위에서 visitedQueue에 추가된 값)에 연결된 간선들을 모두 needVisitQueue에 추가한다.
5. 그리고 다시 2번부터 작업을 한다.

visitedQueue

A

B

C

D

E

F

needVisitQueue

 

결과적으로 위와 같이 큐에 저장이 된다. 

 

 

이 과정을 코드로 나타내면 아래와 같다.

func BFS(graph: [String: [String]], start: String) -> [String] {
    var visitedQueue: [String] = []
    var needVisitQueue: [String] = [start]
    
    while !needVisitQueue.isEmpty {
        let node: String = needVisitQueue.removeFirst()
        if visitedQueue.contains(node) { continue }
        
        visitedQueue.append(node)
        needVisitQueue += graph[node] ?? []
    }
    
    return visitedQueue
}

 

시간 복잡도

일반적으로 노드 수(V), 간선 수(E)라 했을 때 시간 복잡도는 O(V+E)이다. (입력 자체를 노드와 간선을 기준으로 받기 때문이다.)