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

 

 

 

안녕하세요 :) 소들입니다!!!

이번 포스팅에선 너비 우선 탐색(BFS)에 대해 알아보려고 해요!!!!

먼저, 너비 우선 탐색이란 그래프를 탐색하는 방법 중 하나인데,

그래프를 모르면 이해할 수 없으니, 혹시 그래프를 모르면 이 포스팅을 꼭! 먼저 읽고 와주세요

 

그래프가 알고리즘? 자료구조? 중에 어려운 축에 속해서..

쉽게 이해하실 수 있게 노력해보겠습니다 :) 깊이 우선 탐색은 다음 포스팅에서!!

모든 포스팅은 편의 말투로 합니다~!!

 

 

 

 

1. 너비 우선 탐색(BFS)이란?

 

너비 우선 탐색이란 Breadth-First Search로,

보통 BFS라고들 많이 부름!!! :) 머 정의는 다음과 같은데..

 

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

 

음.. 정의만 보면 역시 이해가 안 갈 테니까:)

너비 우선 탐색 방식에선,  다음과 같은 순서로 그래프의 노드를 탐색함!!

 

 

 

 

숫자가 순서라고 생각하면 됨!!!

탐색 노드부터 인접한 노드들을 탐색하고,

다 탐색하면, 인접한 노드들의 인접한 노드들부터 탐색 하는 것임! 

따라서 같은 레벨에 있는 노드들부터 탐색하는 것처럼 보여짐 :)

 

참고로 너비 우선 탐색에서 내 인접 노드들 중에서,

왼쪽을 먼저 탐색하냐, 오른쪽을 먼저 탐색하냐 같은 순서는 중요하지 않음!

어디를 먼저 탐색하더라도, 같은 레벨에 있는 노드를 먼저 다 탐색해야 다음 레벨 노드를 탐색할 수 있음!

 

 

 

 

2. 코드로 구현 해보기

 

2-1. 탐색할 그래프 미리 만들어두기

 

음.. ~ 여기선 데이터를 갖고 그래프를 어떻게 구현하냐!는 다루지 않음

다만, 이미 구현되어 있는 그래프를 어떻게 탐색하는지만 다룰 것임 :)

 

따라서, 탐색할 그래프를 미리 딕셔너리 형태로 만들어 두겠음

그래프를 표현하는 방법엔 두 가지 방법이 있다고 이전 포스팅에서 배웠음!

그중에 인접 리스트 방식으로 다음과 같이 나타낼 수 있고,

 

 

 

 

이를 하드코딩으로 하면..ㅎ

 

 

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

 

 

요롷게..ㅎ

 

 

 

2-2. 너비 우선 탐색을 하는 방법

 

너비 우선 탐색은 보통 두 개의 큐(Queue)로 구현함!!!!

 

방문 해야하는 노드를 저장하는 Queue(이하,needVisitQueue)

이미 방문한 노드를 저장하는 Queue(이하, visitedQueue)

 

이렇게 두 가지 큐로 구현할 수 있음!!

 

 

 

 

이렇게!!  👀

자 만약 A부터 탐색을 한다고 하면, 어떤 방식으로 탐색하는지 봐볼  것임

 

 

 ① 탐색할 노드의 데이터를 needVisitQueue에 넣는다 

 

 

 

 

 ② needVisitQueue의 첫 번째 값을 추출해서(FIFO), visitedQueue에 해당 값이 존재하는지 확인한다 

 

 

 

 

만약, visitedQueue에 추출한 값이 존재하면,

추출한 값은 버리고 그 다음 첫번째 값을 추출(FIFO)하여, 다시 visitedQueue에 존재하는지 확인함

위 과정을 visitedQueue에 존재하지 않는 값이 나올 때까지 반복하는데,

그러다가 needVisitQueue가 텅~ 비면 그때 탐색이 끝나는 것임:)

 

근데, 만약 위처럼 visitedQueue에 추출한 값이 존재하지 않으면 다음 ③번 과정을 진행함!

 

 

 ③ 추출된 값이 visitedQueue에 존재하지 않으면, visitedQueue에 추가한다 

 

 

 

 

 ④ 추출된 값(방금 visitedQueue에 추가된 값)에 연결된 간선들을

모두 needVisitQueue에 추가한다 

 

 

 

 

위 작업까지 했으면,

needVisitQueue가 빌 때까지 다시 ②번부터 반복함

 

 

.

.

한번 따라서 쭉 ~ 해보셈!! 그럼 마지막엔 visitedQueue에 다음과 저장되어 있을 것임 :)

 

 

 

 

needVisitQueue가 모두 비었을 경우, visitedQueue에 채워진 값들이

너비 우선 탐색을 통해 탐색된 노드들의 순서임 :)

 

 

 

2-3. (이번엔 진짜) 코드로 구현하기

 

탐색할 그래프를 위에서 만든 것을 쓴다고 하면,

너비 우선 탐색은 다음과 같이 구현할 수 있음 :)

 

 

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
}

 

 

Queue라서 removeFirst인 것임! FIFO ㅎㅎㅎ

코드가 어렵지 않아서 :) 위 과정을 이해 했으면 쉽게 따라올 수 있어용

 

 

 

 

3. 너비 우선 탐색(BFS)의 시간 복잡도

 

일반적으로 노드 수(V), 간선 수(E)라 했을 때 시간 복잡도는

 

O(V+E)

 

가 됨...! 입력 자체를 노드와 간선으로 받기 때문에..👀

 

 

 

 

 

 

.

.

.

흠 그래프를 (하드 코딩이 아닌) 배열로 표현하는 코드는 나중에 공부하고 포스팅 하겠음!! :)

혹시 피드백, 이해 안 가시는 점은 언제든 댓글 남겨주세요~~