[Algorithm] BFS (Breadth First Search)

1. BFS란?

BFS는 너비 우선 탐색으로, 그래프를 층별로 탐색하는 것이다.

자세히 얘기하자면, 한 노드를 방문했을 때 그 노드의 모든 자식 노드를 방문해야 다음 노드로 갈 수 있다.

이 과정을 루트 노드부터 시작해서 모든 리프 노드를 방문할 때까지 반복한다.

DFS와 달리 모든 리프 노드를 방문했다면 탐색이 끝난 것이므로 (맨 아래층에 있으므로) 종료한다.

 

예제를 통해 살펴보자. 다음과 같은 그래프를 너비 우선 탐색으로 탐색하고자 한다. 

먼저 루트 노드인 9를 방문한다. 이후 9의 자식 노드인 8과 6을 방문한다. 자식 노드를 방문했으면, 자식 노드 중 가장 왼쪽으로 이동해 그 노드의 자식들을 모두 방문한다. 여기서는 5와 2가 된다. 이후 오른쪽 노드로 이동해 자식을 방문한다. 여기서는 1이 된다. 따라서 이동 순서는 9 > 8 > 6 > 5 > 2 > 1이 된다.

 

구현에는 큐를 쓴다. 큐는 먼저 들어온 원소가 먼저 나가는 구조이므로, 모든 자식 노드를 방문한 이후 그 자식들의 부모가 되는 노드를 방문하기 적합하다. 위의 그래프로 예를 들자면, 먼저 9가 큐에 들어가고, 9을 빼면서 9의 자식인 8과 6이 들어간다. 이 때 큐는 [8, 6]이 된다. 이 때 큐를 이용하면 방문해야 하는 9의 왼쪽 자식 노드, 즉 8을 바로 뺄 수 있다. 

 

2. 구현

 

이진 트리에서의 BFS 코드이다. 

 

from collections import deque

q = deque()
graph = list(map(int, input().split()))
n = len(graph)
visited = [-1 for _ in range(n)]
res = []
q.appendleft(0)

while len(res) != len(graph):
    present = q.popleft()
    print(present)
    if visited[present] == -1:
        visited[present] = 0
        q.appendleft(present)
        res.append(graph[present])

    left = 2 * present + 1
    right = 2 * present + 2

    if left < n:
        q.append(left)
    if right < n:
        q.append(right)

print(res)

결과에 반영되는 연산은 모두 present에서 해야 한다. 현재 노드에서만 결과 삽입 연산을 해야 중복을 방지할 수 있기 때문이다.

queue는 방문할 순서를 담은 자료구조라는 것을 기억하자.