너비 우선 탐색(BFS)

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 사용해보면서 배운 점을 정리한 글입니다.

그래프의 각 정점을 방문하는 그래프 순회에는 다양한 방법이 있으나 크게 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 2가지로 나눌 수 있다. 이번엔 BFS에 대해 정리하고자 한다.

BFS(너비 우선 탐색)?

Breadth First Search의 약자로 시작 노드에서 시작한 뒤 다음 길이로 진행하기 전 출발점에서 발생한 모든 분기를 탐색한 후 다음 레벨로 진입한다. 갈림길의 모든 지점들을 탐색한 뒤 각 갈림길에서 발생한 모든 갈림길을 다시 순차적으로 탐색하는 모습이 가로로 훑는 모양새다.

BFS의 경우 무한 루프나 스택오버플로우의 우려가 있었지만 BFS의 경우 모든 경로에 대해 동시에 탐색을 진행하므로 그럴 걱정은 없다.

BFS의 특성

• BFS는 재귀적으로 구현할 수 없다.
• 두 노드 사이의 최단 경로나 임의의 경로를 구하는 데 사용한다.
• DFS보다 검색에서 유리하다 (DFS는 조건을 만족하는 순회에 초점)
• 방문한 노드들을 저장한 후 차례대로 꺼내는 FIFO(선입선출) 방식으로 탐색을 진행하기에 큐를 사용한다.

BFS의 장점

• 해가 여러 개라도 가장 먼저 구한 해가 최단 경로임을 보장한다. (너비 탐색이기 때문)
• 최단 경로가 존재한다면 특정 경로의 길이가 무한이라도 최단 경로를 찾을 수 있다.

BFS의 단점

• DFS는 재귀 호출로 발생한 중간값만을 스택에 저장하지만 BFS는 큐에 탐색할 노드들을 저장하므로 저장 공간을 많이 요구한다. (메모리 소모 UP)
• 노드의 개수가 많아지면 효율성이 떨어진다.

BFS의 구현

graph = {1: [2, 3, 4], 2: [5, 6], 3: [8],
         4: [8, 9],    5: [7],    6: [],
         7: [3],       8: [],     9: []}

def bfs_queue(start):
    path = [start]
    q = [start]
    while q:
        v = q.pop()
        for x in graph[v]:
            if x not in path:
                path.append(x)
                q.append(x)
    return path

print(f'bfs_queue path: {bfs_queue(1)}')