[Swift] BFS(Breadth-First Search, 너비 우선 탐색)에 대해서 알아보자

안녕하세요~ 

 

오늘은 너비 우선 탐색에 대해서 정리하려고 합니다.

 

 

너비 우선 탐색( BFS, Breadth-First Search )이란?

 

너비 우선 탐색은 인접한 노드들을 우선으로 탐색하는 방식을 말합니다. 

 

아래의 이미지에 있는 그래프에서 BFS를 사용하면

 

 

 

앞서 말한 것처럼 인접한 노드부터 확인하게 되는데

예를 들어서 1을 가장 먼저 탐색하고 나면 인접한 8, 5, 2를 순서대로 탐색합니다.

 

다음은 6부터 시작해서 9까지 탐색을 진행하겠죠?

 

즉, 같은 레벨에 있는 노드들부터 탐색을 하는 것입니다.

여기서 8부터 시작하든 2부터 시작하 든 순서는 중요하지 않습니다. 

중요한 점은 같은 레벨에 있는 노드를 전부 탐색하고 다음 레벨로 넘어간다는 것입니다.

 

✔︎ Swift로 구현해 보기

위의 이미지에 있는 그래프를 통해 BFS를 구현해 보자.

 

1. 큐( Queue )

 

BSF는 보통 두 개의 큐로 구현합니다.

 

큐는 지난 포스팅에서 다뤘으니 여기서 참고하시면 될 것 같습니다.

 

(1) 방문한 노드를 저장하는 큐

(2) 방문해야 하는 노드를 저장하는 큐

 

2. 인접리스트( Adjacency List )

 

그래프를 표현하는 방법에는

인접 행렬 그래프와 인접 리스트 방식 두 가지가 존재합니다.

 

여기서는 인접 리스트 방식을 사용해 설명하겠습니다.

인접리스트란 말 그대로 인접한 노드들을 리스트로 나열한 것을 말합니다.

 

1	8	5	2
8	1	6	4	3
5	1
2	1	9
6	8	10	7
4	8
3	8
9	2
10	6
7	6

 

위의 값들을 딕셔너리로 구현하면 아래와 같습니다.

 

let graph: [String: [Int]] = [
    "1" : [8, 5, 2],
    "8" : [1, 6, 4, 3],
    "5" : [1],
    "2" : [1, 9],
    "6" : [8, 10, 7],
    "4" : [8],
    "3" : [8],
    "9" : [2],
    "10" : [6],
    "7" : [6]
]

 

2. BFS

설명은 주석으로 하겠습니다.

 

func breadthFirstSearch(graph: [String: [Int]], start: String) -> [String] {

    // 이미 방문한 노드를 저장하는 큐
    var visitedQueue: [String] = []
    // 방문해야하는 노드를 저장하는 큐
    var needVisitQueue: [String] = [start]
    
    while !needVisitQueue.isEmpty {
        
        let node: String = String(needVisitQueue.removeFirst())
        
        // 이미 방문했던 노드라면 continue 처리
        if visitedQueue.contains(node) {
            continue
        }
        
        visitedQueue.append(node)
        // 인접한 노드를 추가하는 과정입니다.
        // 만약 가장 처음에 "1"이 들어온다면 1과 인접한 리스트를 needVisitQueue에 추가하는 과정
        needVisitQueue += graph[node].map{ $0.map { String($0) } } ?? []
    }
    
    return visitedQueue
}

print(breadthFirstSearch(graph: graph, start: "1"))
// ["1", "8", "5", "2", "6", "4", "3", "9", "10", "7"]

 

여기까지 정리하겠습니다.

그럼 안녕 ~ 👋🏻 👋🏻 👋🏻