너비 우선 탐색(BFS)

너비 우선 탐색(BFS)

다른 레벨로 이동하기 전에 같은 뎁스에 있는 모든 노드를 탐색하는 그래프 탐색 알고리즘 소스 노드에서 시작하여 그래프를 뎁스로 탑색하며, 다음 뎁스로 내려가기 전에 인접한 모든 노드를 방문한다.

개요

가중치가 없는 그래프에서 최단 경로를 찾거나, 특정 최적화에서 최적의 솔루션을 찾는데 널리 사용된다.

동작 과정

BFS 알고리즘은 큐(Queue) 자료구조를 이용하여 구현.

1. 시작노드 선택

2. 큐를 생성하고 시작노드를 큐에 대기

3. 시작노드를 방문한 노드로 표기

4. 큐가 비워질 때 까지 5,6 반복

5. 큐에서 첫번째 노드를 큐에서 해제하고 방문한 노드로 표기

6. 큐에 대기중인 노드 중 아직 방문하지 않은 인접 노드 모드 탐색, 그 후 이 노드들을 방문한것으로 표기하고 큐에 대기열 추가

7. 모든 노드 방문시 알고리즘 종료

응용

• 네트워크 탐색 및 발견

• 연결된 구성 요소와 이분 그래프 찾기

예시

아래는 BFS + 백트래킹을 이용하여 N-Queen 문제를 해결하는 방법.

import Foundation

func checkQueen(_ arr: [Int], _ index: Int) -> Bool {
    for i in 0..<index {
        if arr[i] == arr[index] || abs(arr[i] - arr[index]) == abs(i - index) {
            return false
        }
    }
    return true
}

func backtrack(_ n: Int, _ cnt: Int, _ arr: inout [Int], _ answer: inout Int) {
    if cnt == n {
        answer += 1
        return
    }

    for i in 0 ..< n {
        arr[cnt] = i
        if checkQueen(arr, cnt) {
            backtrack(n, cnt + 1, &arr, &answer)
        }
    }
}

func solution(_ n: Int) -> Int {
    var answer = 0
    var arr = Array(repeating: 0, count: n)
    
    backtrack(n, 0, &arr, &answer)
    
    return answer
}

let n = 9 // 입력값
print(solution(n)) // N-Queens 알고리즘 결과 출력

시간 복잡도

O(V+E)