너비 우선 탐색 (Breadth-first search, BFS)

그래프를 탐색하는 방법에는 크게 너비 우선 탐색(BFS)와 깊이 우선 탐색(DFS) 두 가지가 있는데, 먼저 너비 우선 탐색에 대해 알아보도록 하자.

너비 우선 탐색

너비 우선 탐색은 가장 먼저 시작 정점을 방문한 후, 그 시작 정점과 인접한 모든 정점들을 우선적으로 탐색해나가는 방법이다.
시작 정점부터 목표 지점까지의 모든 경로들을 동시에 탐색이 가능하며, 간선의 가중치가 1인 경우 목표 지점까지의 최소 비용(최단 거리)를 구하는 문제에 활용이 가능하다.
※ 이미지 출처: guru99.com

BFS 구현 : Queue

BFS를 구현에는큐(Queue)의 First In First Out 구조를 활용한다. 특정 정점에 인접한 모든 정점들을 큐에 저장한 후 하나씩 꺼내오면서 방문하고, 다시 해당 정점의 인접한 모든 정점들을 큐에 저장한다.
그리고 또 하나 중요하게 있는데, 이미 방문한 정점을 다시 방문하지 않도록 방문 여부를 나타내는 리스트를 따로 만들어 둬야한다는 것이다. 큐에 인접 정점들을 삽입할 때는 이 리스트를 확인해 아직 방문하지 않은 정점들만 큐에 삽입하고, 큐에서 꺼내올 때는 이 리스트에 방문 표시를 해둔다.

BFS 알고리즘

1. 시작 정점을 큐에 삽입한다.
2. 큐에서 정점을 하나 꺼내와 방문 표시를 한다.
3. 꺼내온 정점과 인접한 정점 중 아직 방문하지 않은 정점들을 큐에 삽입한다.
4. 큐에 저장된 정점이 없을 때 까지 2-3번 과정을 반복한다.
   
   

DFS 코드 (Python)

# 그래프 탐색 (BFS)
from collections import deque

def bfs(graph, start):
    visited = []
    queue = deque()

    # 시작노드 큐에 담기
    queue.append(start)

    # 방문 노드와 연결된 모든 노드들을 담고 하나씩 방문
    while queue:
        # 큐의 맨 앞 노드 빼오기
        now = queue.popleft()
        # 아직 방문하지 않았다면 방문 마크 후 인접 노드들 큐에 넣기
        if now not in visited:
            visited.append(now)
            queue.extend(graph[now])

    return ' '.join(visited)

graph = {
    'A': ['B'],
    'B': ['A', 'H', 'C'],
    'C': ['B', 'D'],
    'D': ['C', 'E', 'G'],
    'E': ['D', 'F'],
    'F': ['E'],
    'G': ['D'],
    'H': ['B', 'I', 'J', 'M'],
    'I': ['H'],
    'J': ['H', 'K'],
    'K': ['J', 'L'],
    'L': ['K'],
    'M': ['H']
}

print(bfs(graph, 'A'))

BFS를 활용한 문제 해결

대표적인 그래프 탐색 문제를 BFS를 활용해 해결해보자.

코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 네트워크

# 네트워크(BFS)
from collections import deque

def solution(n, computers):
    ans = 0
    visited = [False] * n  # 방문 여부를 표시할 리스트
    q = deque()
    while False in visited:
    	# 1. 시작 정점 큐에 삽입
        q.append(visited.index(0))
        while q:
	    # 2. 큐에서 정점 하나를 꺼내와 방문 표시
            node = q.popleft()
            visited[node] = True
            for i in range(n):
                # 3. 인접한 정점 중 아직 방문하지 않은 정점들을 큐에 삽입
                if not visited[i] and computers[node][i] == 1:
                    q.append(i)
        ans += 1
        # 4. 큐에 저장된 정점이 없을 때 까지 2-3번 과정을 반복
    return ans