11장 너비 우선 탐색(BFS)[PYTHON]

목차
1. BFS
2. 그림으로 이해
3. 코드
4 느낀점

BFS

BFS는 그래프를 완전 탐색하는 방법 중 하나이다.
출발 노드에서 시작해 가까운 노드를 먼저 다 방문하는 것이 DFS와의 차이점이다.
DFS에서는 재귀함수를 이용하는 반면 BFS에서는 큐 자료구조를 이용한다.
파이썬에서는 큐를 덱을 이용하여 구현한다.

그림으로 이해

아래와 같은 그래프가 존재할 때 1번 노드를 시작노드로 하여 BFS탐색을 하게되면 다음과 같다.







DFS와는 다르게 데이터 저장에 대해 로직이 단순하기 때문에 바로 코드로 이해하는 것이 빠를 것 같다.

코드

from collections import deque
graph = [[],
         [2, 3],
         [4],
         [5, 6],
         [],
         [],
         []]

def BFS(start):
    Queue = deque()
    Queue.append(start)
    while Queue:
        p = Queue.popleft()
        print('{0}번 노드 탐색!'.format(p)) # 어떤 노드를 탐색하는 지 알려주는 부분
        for x in graph[p]:
            Queue.append(x)

BFS(1)

위 코드는 BFS 자체만 구현한 것이다.
실제 문제에서는 조건에 따라 더 복잡해지는 경우가 많다.

느낀점

DFS를 설명하는 것보다는 BFS에 대해 설명하는 것이 더 쉬웠던 것 같다.
파이썬에서 종종 'recursion error'가 뜨는데 이럴때마다 BFS를 이용하여 푼 문제들이 많았던 것 같다.
BFS 알고리즘도 매우 중요한 알고리즘중 하나이니 잘 숙지해두자.