[알고리즘] 너비우선탐색 (BFS : Breath First Search)

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

• 한 노드에서 가장 인접한 다른 노드부터 차례로 그래프를 탐색하는 알고리즘이다.
• 가장 가까운 노드부터 가장 먼 노드까지 방문하기 때문에 넓게 탐색한다. (그래서 '너비'우선탐색)
  
• Queue에 인접한 노드들을 넣어놓고 차례대로 deQueue한다.
• 두 노드의 최단 경로 또는 임의의 경로를 찾아야할 때 주로 사용한다.

그래프(Graph)에 대한 포스팅은 다음에 해야겠다.

너비우선탐색(BFS)의 특징

• 깊이우선탐색(DFS)보다 검색 속도가 빠르다.
• 모든 노드를 다 탐색해야 하기 때문에 많은 수의 노드를 가진 그래프에서는 효율적이지 않다.
• 재귀를 사용하지 않는다. (깊이우선탐색은 재귀를 사용한다.)

너비우선탐색(BFS)의 작동 원리

출처 : 위키피디아

코드 구현

from collections import deque

def BFS (graph, start_node) :
    visited = list()
    queue = deque()
    
    queue.append(start_node)
    
    while queue :
        node = queue.pop()
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])
    return visited