[Algorithm] 너비우선탐색(BFS,Breadth-First-Search)란?(feat.Swift)

안녕하세요 Foma 👟 입니다!

오늘은 트리를 탐색하는데 쓰이는 알고리즘인 너비우선탐색(BFS)에 대해서 알아보도록 하겠습니다.

 

바로 시작할게요~

---

BFS란?

 

너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. 큐를 사용해야만 레벨 순서대로 접근이 가능하다. - 위키 백과 -

 

쉽게 예제를 통해서 설명드릴게요!

 

아래 사진과 같이 지구 안에 세 나라만 있고 모든 나라와 나라의 도시들을 탐색한다고 가정하겠습니다.

 

 

탐색하는 방법은 여러가지가 있겠지만

 

먼저 지구에 있는 나라를 왼쪽부터 어떤 도시들이 있는지 확인하고 넘어가는 방법은 DFS입니다.

 

(혹시 DFS를 모르시는 분들은 여기 에서 확인해주세요!)

 

BFS는 먼저 지구에서 시작해서 너비(가로)부터 우선적으로 탐색합니다.

 

지구 -> 한국 -> 미국 -> 영국 ... 순으로 탐색을 하는 것이죠!

 

즉, 루트  노드에서부터 시작해 자신과 인접한 노드를 탐색하고 그 아래 레벨로 가는 탐색 방법입니다.

 

 

 

 

탐색하는 순서는 아래와 같이 진행됩니다.

 

출처: 위키백과

---

코드 구현

 

이제 코드로 확인해볼까요?

 

먼저 정점의 갯수를 설정해줍니다.

 

 

let n:Int = 13

 

각 정점에 대한 이름을 순서대로 넣어줍니다.

 

 

let world = ["지구","한국","미국","영국","서울","부산","광주","뉴욕","LA","시카고","런던","맨체스터","리버풀"]

 

지구 = 0 ,

한국 = 1, 미국 = 2, 영국 = 3,

서울 = 4, 부산 = 5, 광주 = 6,

뉴욕 = 7, LA = 8, 시카고 = 9,

런던 = 10, 맨체스터 = 11, 리버풀 = 12 

 

로 해당 이름 인덱스를 연결로 세팅해줍니다.

 

무작위로 정점이 연결된 정보들을 세팅해줍니다.

 

let allConnections:[[Int]] = [[0,1],[2,0],[0,3],[4,1],[5,1],[1,6],[2,7],[2,8],[9,2],[3,10],[3,11],[12,3]]

 

정점에 대한 연결을 방문했는지를 표시할 visited 이중배열과

 

정점의 순서들을 담을 큐를 만들어줍니다. (시작 정점인 0을  초기값으로 넣어줍니다.)

 

var visited:[[Bool]] = Array(repeating: Array(repeating: false, count: n), count: n)
var queue:[Int] = [0]

 

본격적으로 BFS를 구현하는데 가장 핵심은 while문을 이용해서 큐가 아무것도 없을 때까지 반복하는 것입니다.

 

먼저 가장 큐에 가장 첫 번째 있는 숫자를 꺼내옵니다.

 

그리곤 모든 연결 중에서 첫 번째 숫자와 연결된 숫자를 큐에 담는데 

 

만약 부모 노드이거나 인접한 노드일 경우 무한 루프가 발생하게 됩니다.

 

고로 visited에 꼭 이 현재 first와 정점 간에 이미 방문했는지를 체크하고 하지 않았다면 큐에 넣어줍니다.

 

func searchByBFS(queue:inout [Int],visited:inout [[Bool]]) {
    while !queue.isEmpty {
        let first = queue.removeFirst()
        print(world[first])
        allConnections.forEach{
            if $0[0] == first && !visited[$0[1]][first] {
               visited[$0[1]][first] = true
               visited[first][$0[1]] = true
                queue.append($0[1])
            }
            
            if $0[1] == first && !visited[$0[0]][first] {
               visited[$0[0]][first] = true
               visited[first][$0[0]] = true
                queue.append($0[0])
            }
        }
    }
}

 

이렇게 실행하고 출력해보면 아래와 너비 우선으로 탐색된 것을 볼 수 있습니다!

 

searchByBFS(queue: &queue, visited: &visited)

//지구
//한국
//미국
//영국
//서울
//부산
//광주
//뉴욕
//LA
//시카고
//런던
//맨체스터
//리버풀

---

전체 소스 코드