BFS 이론

BFS(깊이 우선 탐색)은 그래프에서 가까운 노드부터 탐색하는 알고리즘이다. 큐 자료구조를 이용한다.

다음과 같은 과정으로 동작한다. DFS와 마찬가지로 한 번 방문한 노드는 다시 방문하지 않는다. 따라서 방문 처리 리스트를 만들어 방문을 처리해 주며 노드에 접근하도록 한다.

1. 큐에 시작노드를 넣고 방문처리한다.
2. 큐에서 노드를 꺼내고, 해당 노드의 인접 노드 중 아직 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리 한다.
3. 모든 노드를 다 탐색하거나 문제를 해결해 더이상 탐색할 필요가 없을 때까지 2번 과정을 반복한다.

강의에서 주어진 그래프이다.

위와 같은 그래프가 있고, 시작 노드는 1이며 번호가 낮은 인접노드부터 방문한다고 하자.

• 시작노드 방문 처리 및 큐에 넣기. 큐 : 1
• 큐에서 1 빼고 1의 인접노드인 2 3 8방문처리 후 큐에 삽입. 큐 : 2-3-8
• 큐에서 2 빼고 2의 인접노드 중 아직 방문하지 않은 7 삽입 : 큐 : 3-8-7
• 큐에서 3빼고 3의 인접노드 4 5 큐에 삽입. 큐 : 8-7-4-5
• 큐에서 8 뺌. 8에는 방문하지 않은 인접노드가 없으므로 삽입 x. 큐 : 7-4-5
• 비슷한 방식으로 7 빼고 7의 인접노드 6 삽입. 큐 : 4-5-6
• 4, 5, 6은 방문 안한 인접노드가 없으므로 하나씩 뺌.
• 탐색 순서 : 1 - 2 - 3 - 8 - 7 - 4 - 5 - 6

이를 코드로 구현해보면 아래와 같다.

from collections import deque

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]
visited = [False] * 9
visited[1] = True
queue = deque([1])
while queue:
    node = queue.popleft()
    print(node, end = ' ')
    for adjNode in graph[node]:
        if not visited[adjNode]:
            visited[adjNode] = True
            queue.append(adjNode)
# 1 2 3 8 7 4 5 6

노드는 보통 1부터 시작하므로 그래프 리스트의 첫 번째 요소는 사용하지 않는 것이 일반적이다. 큐가 비어있지 않다면 반복하여 실행해 준다. 큐에서 한 노드를 꺼내서 그 노드의 인접노드에 접근한다. 인접노드가 방문하지 않은 노드라면 방문처리 해주고 큐에 넣어준다. 다음 게시글에서 예제문제를 풀어보자.