[Algorithm/Swift] BFS(너비 우선 탐색) Swift로 구현해보기

안녕하세요 제인입니다:)

오늘은 저번 알고리즘 포스팅(DFS)에 이어 BFS(너비 우선 탐색)에 대해 정리해보려 합니다!

시작하기 전에, 탐색 알고리즘 중 하나인 BFS를 이해하려면 우선 그래프에 대한 이해부터 필요하니

혹시 그래프에 대해 잘 모르신다면 아래 링크로 걸어둔 이전 포스팅을 참고해주시면 좋을 것 같습니다!!

[Algorithm/Swift] DFS(깊이 우선 탐색) Swift로 구현해보기

BFS

BFS(Breadth First Search)는 '너비 우선 탐색'이라는 의미를 가집니다.

쉽게 말해 그래프의 가까운 노드부터 탐색하는 알고리즘입니다!

지난 포스팅에서 정리했었던 DFS는 그래프의 가장 깊은 곳, 즉 가장 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작하는 알고리즘이었는데요, BFS는 그 반대로 인접한 노드들을 우선으로 탐색하는 방식입니다.

너비 우선 탐색 방식의 탐색 순서를 그림으로 나타내보자면, 위와 같습니다!

1번 노드부터 탐색을 시작한다고 하면 인접한 노드들을 탐색하고, 탐색이 끝나면 방금 탐색했던 노드의 인접한 노드를 탐색합니다.

이 때, 현재 노드의 인접 노드들 중에서 어떤 노드를 먼저 탐색하는지는 중요하지 않습니다. 

위의 예시에서 2, 3번이 바뀌어도 되고, 4, 5, 6번 노드들 중 어느 것 먼저 탐색해도 상관없다는 것이죠!

즉, 같은 레벨에 있는 노드들 중에서는 어느 것 먼저 탐색하느냐는 중요하지 않고, 현재 노드에서 인접한 같은 레벨에 있는 노드들의 탐색이 끝나면, 다음 레벨의 노드들의 탐색으로 넘어간다고 생각하면 좋을 것 같습니다!

BFS 구현방법

그렇다면 BFS는 실제로 어떤 방식으로 구현할 수 있을까요??

BFS는 보통 선입선출(FIFO) 방식인 큐(Queue) 자료구조를 이용하여 구현합니다!

인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 됩니다. 

알고리즘의 정확한 동작 방식은 다음과 같습니다.

 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다.

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 합니다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다.

 

이제 간단한 예제로 실제 코드를 보면서 BFS를 이해해봅시다!

 

위와 같은 구조의 그래프를 1번 노드를 시작 노드로 설정하여 BFS를 이용해 탐색을 해보도록 하겠습니다.

 

가장 먼저 시작 노드인 1을 큐에 삽입하고 방문 처리를 합니다. 

큐에서 노드 1을 꺼내고 다음으로 1번 노드의 인접 노드들을 큐에 삽입해야하는데,

위의 그래프에서 1번 노드와 연결된 인접 노드는 2, 3, 8 이렇게 세 개가 있으니 모두 큐에 삽입하고 방문 처리를 합니다.

그 다음으로, 삽입한 노드들 중 먼저 2번 노드를 꺼내고 방문하지 않은 2번 노드의 인접 노드인 7을 큐에 삽입하고 방문 처리를 합니다.

다음은 3번 노드를 꺼내주고 3번 노드의 인접 노드들인 4, 5를 큐에 삽입 후 방문 처리를 해줍니다.

이제 8번 노드를 꺼내줄 차례인데, 8번 노드의 인접 노드들 중 방문하지 않는 노드는 없으므로 현재 단계에서 삽입할 노드는 없겠죠?

그렇다면 바로 다음 노드인 7번 노드를 꺼내 줍니다. 7번 노드의 인접 노드 중 방문하지 않은 노드인 6을 큐에 삽입하고 방문 처리를 합니다.

이제 방문하지 않은 노드가 없으므로 큐에 남아있는 노드를 차례로 꺼내주면 탐색 과정이 끝나게 됩니다.
결과적으로 노드의 탐색 순서(=큐에 삽입된 순서)는 1 -> 2 -> 3 -> 8 -> 7-> 4 -> 5 -> 6 이 됩니다.

 

위의 과정을 코드로 구현한다면 아래와 같이 구현할 수 있습니다.

 

// 2차원 배열
let graph = [[],
             [2, 3, 8],
             [1, 7],
             [1, 4, 5],
             [3, 5],
             [3, 4],
             [7],
             [2, 6, 8],
             [1, 7]]

func bfs(_ graph: [[Int]], _ start: Int) -> [Int] {
    
    var visitedQueue = [Int]() // 방문한 노드 저장하는 배열
    var needVisitQueue = [start] // 방문할 노드 저장하는 배열
    
    while !needVisitQueue.isEmpty {
        let node = needVisitQueue.removeFirst() // 큐는 FIFO로 동작
        if visitedQueue.contains(node) { continue } // 이미 방문한 노드라면 아래 과정 건너 뜀
        
        visitedQueue.append(node) // 현재 노드 방문처리
        needVisitQueue += graph[node]
    }
    
    return visitedQueue
}

// 시작 노드를 1로 설정하여 함수 호출
bfs(graph, 1) // [1, 2, 3, 8, 7, 4, 5, 6]

 

---

[참고 자료]

Swift) 너비 우선 탐색(BFS) 구현 해보기

<이것이 코딩 테스트다 with 파이썬>

이것이 취업을 위한 코딩 테스트다 with 파이썬 | 나동빈 - 교보문고