[알고리즘] BFS(너비 우선 탐색) 알고리즘 이란

 

BFS(너비 우선 탐색) 알고리즘의 개념

 

트리 혹은 그래프를 탐색하는 기법 중 하나로 시작 노드에서 자식의 노드들을 순서대로 탐색을 하면서 방문할 수 있는 인접한 노드들을 우선으로 탐색하는 알고리즘 입니다. 

자료구조는 Queue 또는 Array 를 통하여 구현 가능합니다.

 

 

BFS 탐색 과정

 

출처 https://developer-mac.tistory.com/64

 

 

 

큐를 사용하였을때 탐색 과정을 설명하면은

 

1. 시작 노드 1을 방문하여 1의 노드에서 방문 가능한 2, 3 ,4 를 큐 안에 넣습니다 [ 2, 3, 4 ]

2. 큐에 있는 2 , 3 , 4 를 꺼내 방문할수 있는 곳을 큐에 추가해줍니다. [ 5, 6, 7, 8 ]

3. 5, 6, 7, 8 노드도 2번 과정을 반복해줍니다. 

 

위의 과정을 반복하면 깊이에 따라 차례차례 방문하는것을 확인할 수 있습니다.

1층에 있는 1 번 노드는 2, 3 ,4 추가 

2층에 있는 2, 3 ,4 노드는 5,6,7,8 추가 ...

 

 

 

 

아래의 코드는 Array를 통한 큐 구현 BFS 문제풀이 입니다. 예시로 확인하면 좋습니다.

import Foundation

//백준 1260번
let input = readLine()!
let inputArray = input.split(separator: " ").map{Int(String($0))!}
let (n, m, v) = (inputArray[0], inputArray[1], inputArray[2])
var matrix = Array(repeating: Array(repeating: 0, count: n+1), count: n+1)
var visited = Array(repeating: false, count: n+1)

for _ in 0..<m {
    let input = readLine()!.split(separator: " ").map({Int(String($0))!})
    matrix[input[0]][input[1]] = 1
    matrix[input[1]][input[0]] = 1
}

func bfs(_ v : Int) {
    
    var queue : [Int] = []
    visited[v] = true
    queue.append(v)
    
    while !queue.isEmpty {
        let first = queue.removeFirst()
        print(first, terminator: " ")
        
        for i in 1..<n+1 {
            if visited[i] == false && matrix[i][first] == 1 {
                queue.append(i)
                visited[i] = true
            }
        }
        
    }
    
}

 

 

왜 사용해야할까 or 나만의 고민

가중치가 없는 그래프에서 출발노드에서 목표노드까지 최단 길이 경로를 보장합니다.

경로가 길때 탐색할 노드가 많아지기 때문에 많은 메모리가 필요할 수 있습니다.

깊은 곳에 위치할 경우 DFS 보다 성능이 떨어질 수 있습니다.