BFS 란?(Breadth-First Search)

BFS 알고리즘은 너비 우선 탐색으로 가까운 노드부터 탐색하는 알고리즘.
BFS 구현은 큐(Queue) 자료구조를 이용하는 것이 정석임.
인접한 노드를 반복적으로 큐에 넣게 되면 먼저 들어온 것이 먼저 나가게 되므로 가까운 노드부터 탐색을 진행하게 된다.
이전에 포스팅한 DFS가 재귀로 구현을 한것과는 이 부분에서 차이가 있다.

BFS 탐색 과정

1.첫 노드를 큐에 삽입 후 방문 처리.

2.방문 처리 한 노드를 큐에서 꺼낸다. 그런 뒤에 해당 노드와 인접한 노드 중 방문하지 않는 노드를 전부 큐에 삽입

3.2번 과정을 더 이상 수행할 수 없을 때까지 반복

DFS / BFS 차이

-	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀 함수 이용	큐 자료구조 이용

BFS를 언제 사용해야 할까?

BFS는 너비를 우선 탐색하므로 최단 경로를 탐색할 때 사용하면 효율적임.

BFS 예제

이전과 동일한 그래프를 코드로 구현해보자.

from collections import deque

def bfs(graph,start,visited):
    queue = deque([start])
    visited[start] = True
    lst = []
    while queue:
        node = queue.popleft()
        lst.append(node)
        for i in graph[node]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
    return lst

visited = [False] * 6
graph = [
    [],
    [2,3,4],
    [1,5],
    [1,4],
    [1,3],
    [2]
]
print(bfs(graph,1,visited))

---

참고 자료:
<이것이 코딩 테스트다> - 나동빈
https://velog.io/@songyw0517/BFS%EB%9E%80-%EB%AC%B4%EC%97%87%EC%9D%B8%EA%B0%80
https://kingpodo.tistory.com/48?category=805745