[알고리즘] BFS : 너비 우선 탐색

BFS 개념

• Breadth First Search
• 노드를 방문하고 너비 우선으로 인접한 노드를 방문한다.
• 인접한 노드 중 방문하지 않은 모든 노드들을 저장 후 가장 처음에 넣은 노드를 꺼내서 탐색
• 가장 처음에 넣은 노드 -> 큐(Queue) 이용하는 것이 적합

1. 루트 노드를 큐에 저장

2. 현재 큐의 노드를 빼서 visited 에 추가 (방문처리)

3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가

4. 2부터 반복.

5. 큐가 비면 탐색 종료

BFS 구현

조금 더 확실히 하기 위해 각 노드에 붙은 숫자를 섞어보았다.

위와 같이 DFS인 척 하는 그래프가 있다고 해보자.

우리는 이 그래프를 BFS로 탐색하려고 한다.

그러면 탐색 순서는

이러한 형태가 되어야 할 것이다.

이를 딕셔너리를 사용해 그래프로 나타내면 아래처럼 나타낼 수 있다.

graph = {
	1: [2, 5, 9],
	2: [1, 3],
	3: [2, 4],
	4: [3],
	5: [1, 6, 8],
	6: [5, 7],
	7: [6],
	8: [5],
	9: [1, 10],
	10: [9]
}

이제 이 그래프를 너비 우선 탐색으로 탐색하는 코드를 구현하면 된다.

1. 방문할 노드와 방문한 노드를 저장할 큐, 리스트를 만들어준다.

    visited = [] # 방문한 노드를 저장할 리스트
    q = deque([start]) # 방문해야 할 노드를 저장할 큐

2. 방문해야 할 노드가 남아있는 동안 방문과 방문처리를 반복한다.

    while q: 
        node = q.popleft() # 큐의 가장 처음 노드를 먼저 꺼내서
        visited.append(node) # 방문처리 하고

3. 이 때, 너비 우선이므로 처음 방문한 노드와 인접한 노드를 먼저 다 돌고 다음 노드로 넘어간다. 그 후 방문 노드의 리스트를 리턴해주면 끝

        # graph 딕셔너리에서 해당 노드와 인접한 노드를 돌면서
        for adj in graph[node]:
            if adj not in visited: # 방문하지 않았다면
                q.append(adj) # 방문해야 할 노드를 저장할 큐에 넣는다.

전체 구현 코드

from collections import deque

def bfs_queue(graph, start):
    
    visited = [] # 방문한 노드를 저장할 리스트
    q = deque([start]) # 방문해야 할 노드를 저장할 큐

    # 큐가 비어있지 않은 동안 (방문해야 할 노드가 남아있는 동안)
    while q: 
        node = q.popleft() # 큐의 가장 처음 노드를 먼저 꺼내서
        visited.append(node) # 방문처리 하고

        # graph 딕셔너리에서 해당 노드와 인접한 노드를 돌면서
        for adj in graph[node]:
            if adj not in visited: # 방문하지 않았다면
                q.append(adj) # 방문해야 할 노드를 저장할 큐에 넣는다.

    return visited  

print(bfs_queue(graph, 1)) # [1, 2, 5, 9, 3, 6, 8, 10, 4, 7]