[Python] 너비 우선 탐색, BFS (Breadth First Search) 알고리즘 파이썬 코드

 지난 포스팅을 통해 DFS를 알아보았으니 형제 탐색법인 BFS를 알아보겠다.

BFS 또한 DFS처럼 트리나 그래프를 순회하는 기본 방법 중 하나이다.

 

BFS (Breadth First Search)?

 BFS는 너비 우선 탐색이다. 시작 노드부터 가까운 노드들을 모두 살펴본 뒤 그 다음 노드들을 탐색한다. 단순하게 생각해서 파원에서 파장이 퍼져나가는 모양을 생각하면 얼추 비슷하다.

 

특징과 장단점

- 연결된 모든 노드를 탐색할 수 있다.

- 방문 노드를 기억하고 재방문하지 않는다.

- DFS가 스택을 활용하는 것과 다르게 보통 큐를 활용한다.

- 최단경로 탐색에 적절하다. 해를 찾고나면 다음 해는 찾을 필요가 없기 때문이다.

- 논리 구조가 간단하다.

- 해가 깊은 곳에 있으면 탐색에 오랜 시간이 걸릴 수 있다.

 

 

BFS 동작 원리

 BFS의 동작은 그림으로 간단하게 나타내면 다음과 같다.

 

 첫 시작 노드 1에서 가장 가까운 노드들을 탐색하고, 그 다음으로 1에서 가까운 노드들을 탐색하는 식으로 끝까지 탐색을 한다. 좌우의 우선순위에 따라 그룹 내에서의 순서는 바뀔 수 있지만 대략적인 흐름은 그렇다.

 

 이해를 위해 조금만 더 살펴보자, 이제 큐(Queue)를 도입해서 함께 설명하겠다. DFS와 마찬가지로 일단 1번에서 시작해서 거리가 1인 노드들을 찾는다. 2번 노드와 3번 노드이다. 큐는 스택과 다르게 배열의 앞에서부터 뽑아온다.

 1번 노드를 빼와서 방문하지 않은 노드 중 1번 노드와 연결된 노드들을 queue에 넣어준다. 큐는 [2, 3]이 된다.

 

다음은 큐의 가장 앞에 있는 2를 빼온다. 2와 연결된 노드 중 방문하지 않은 4, 5를 큐에 넣어준다. 

그럼 큐에는 2가 빠지고 3, 4, 5만 남게 된다.

 

마찬가지로 3을 빼고 6, 7을 넣어준다.

 

이런 식으로 큐에서 가장 앞에 있는 노드를 꺼낸 뒤, 그 노드에 연결된 노드 중 방문하지 않은 노드를 큐에 넣어주는 동작을 반복한다. 큐가 빌 때까지 해주면 시작 노드와 연결된 모든 노드를 탐색할 수 있다.

 

이런 방식으로 순회한다면 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 순서로 순회가 이루어진다.

 

BFS Python 코드

# graph는 노드마다 연결된 노드를 저장해 둔 2차원 배열로 가정
## graph[1] = [2, 3], graph[3] = [1, 7]

def bfs(start):
    # 방문 배열과 queue 배열 생성 및 초기값 세팅
    vst = [start]
    q = [start]
    
    # q가 빌 때 까지 수행
    while q:
    	s = q.pop(0) # 가장 먼저 들어온 값을 빼낸다.
        
        # s와 연결된 노드들을 확인하여 방문하지 않은 노드면 추가한다.
        for e in range(graph[s]):
        	if e not in vst:
			q.append(e)
			vst.append(e)
    
    return vst

 

dfs와 마찬가지로 간단한 형태의 while문으로 구현이 가능하다.

 

보통 특정 노드까지의 모든 경로라던지 최단 경로에 포함된 노드들의 집합을 구한다거나, 최단 거리 등을 구하는데 사용된다. 동작 원리와 코드만 이해했다면 어떻게 변형되었다 한들 bfs만으로 풀이하는 문제는 크게 어렵지 않을 것이다.

 

데크 (deque) 같은 라이브러리를 활용하면 조금 더 빠른 연산이 가능하니 찾아보긴 바란다.

 

간단한 BFS 예제

[SWEA] [파이썬 S/W 문제해결 기본] 6일차 - 미로의 거리 (python)