들어가며
이글은 동빈나님의 이코테 강의를 보며 정리한 글입니다. BFS(Breadth First Search)는 너비 우선 탐색입니다. 깊이 우선 탐색과 비슷하지만 우선으로 두는 관점이 다릅니다.
너비 우선 탐색을 구현하기 위해서는 que 자료구조가 사용됩니다. que에 대해서 먼저 알아봅시다.
Que 자료구조
que는 터널과 비슷합니다. 모두 동일한 속도를 가진 자동차가 터널에 일정 간격으로 진입한다고 하겠습니다. 그렇다면 가장 먼저 들어간 자동차가 먼저 나오겠죠? que는 이것과 아주 유사합니다. que 자료구조는 한쪽으로 들어온 자료가 다른방향으로 삭제됩니다. 이는 First-In-First-Out(FIFO)의 특징입니다. 가장 먼저 들어온 자료가 삭제시 삭제되는 것입니다.
python에서는 deque 라이브러리를 이용해서 que를 구현할 수 있습니다. 이 외에도 que를 구현할 순 있으나, 시간복잡도가 상이할 수 있기 때문에 deque라이브러리를 통해서 구현하는 것이 바람직합니다.
from collections import deque
q = deque()
q.append(1) # 1 삽입
# [1]
q.append(2) # 2 삽입
# [1, 2]
q.append(3) # 3 삽입
# [1, 2, 3]
q.popleft() # 왼쪽에서 자료 삭제
# [2, 3]
q.append(4) # 4 삽입
# [2, 3, 4]그러면 이제 본격적으로 BFS 알고리즘에 대해서 알아보겠습니다.
Breadth First Search
BFS는 que를 이용해서 구현할 수 있습니다. 가장 먼저 방문이 시작되는 노드를 방문처리하고 que에 삽입합니다. 이후 que에서 꺼내어 해당 노드와 연결되고 방문하지 않은 모든 노드들을 que에 삽입하고 방문처리합니다. 이제 삽입할 수 있는 노드가 없을 때까지 해당 과정을 반복하면 BFS를 구현할 수 있습니다. 마찬가지로 예시를 보아야겠죠?
아래와 같은 그래프가 있다고 하겠습니다. 노드 1부터 BFS를 수행하겠습니다.
현재 큐 : []
1번 노드부터 방문을 수행하므로 노드 1을 que에 삽입하고 방문처리합니다.
현재 큐 : [1]
이제 1번 노드를 que에서 꺼내고, 해당 노드와 연결된 모든 노드들을 que에 삽입합니다. 2, 3, 4번 노드가 que에 삽입되고 방문처리됩니다.
현재 큐 : [2, 3, 4]
가장 먼저 2번 노드 que에서 꺼내어 연결된 노드 정보를 모두 que에 삽입하고 방문처리합니다.
현재 큐 : [3, 4, 5]
3번 노드를 꺼내어서 확인하지만, 방문하지 않은 노드가 없습니다.
현재 큐 : [4, 5]
4번 노드를 que에서 꺼내어서 연결되어 있는 6번 노드를 que에 삽입하고 방문처리합니다.
현재 큐 : [5, 6]
5번 노드를 꺼내어서 확인하지만, 방문하지 않은 노드가 없기 때문에 다음 과정으로 넘어갑니다.
현재 큐 : [6]
6번 노드를 확인합니다. 연결되어 있는 7번 노드는 아직 방문하지 않았기 때문에 방문처리 후 que에 삽입합니다. 이로써 모든 노드를 방문했습니다.
현재 큐 : [7]
이제 BFS 알고리즘을 python으로 표현해보겠습니다.
from collections import deque
# 각 노드의 연결 노드 정보
graph = [
[],
[2, 3, 4],
[1, 5],
[1, 2, 4],
[1, 3, 6],
[2, 6],
[5, 7, 4],
[6],
]
visited = [False]*8
def bfs(graph, start, visited):
# 시작 노드 que에 삽입
q = deque([start])
# 방문 처리
visited[start] = True
# q가 텅 빌때까지 반복문 수행
while q:
# q에서 자료 꺼냄
v = q.popleft()
print(v, end=' ')
# 연결된 노드 탐색
for i in graph[v]:
# 방문하지 않았다면 que에 삽입 후 방문처리
if not visited[i]:
q.append(i)
visitied[i] = True
bfs(graph, 1, visited)처음에 노드가 연결된 정보를 graph로 표현합니다. 0번 인덱스는 빈 배열인 이유는 노드의 시작 인덱스는 1이므로 사용하지 않기 때문에 빈 배열로 초기화 하였습니다. bfs 함수를 수행하면 맨 처음에 q를 생성해서 시작 노드의 번호를 삽입합니다. 이후, while 반복문을 이용해서 q가 비게 될 때까지 반복문을 수행하면서 q에서 자료를 꺼내어 해당 노드와 연결된 노드 중 방문하지 않은 노드가 있다면 q에 삽입 후 방문처리하게 됩니다. 이 과정에서 방문하지 않은 노드가 사라질 때까지 while반복문은 종료되지 않으므로 모든 노드를 방문할 수 있습니다.
해당 코드를 실행하면 1, 2, 3, 4, 5, 6, 7이 출력됩니다.
