너비 우선 탐색

2025-07-28 00:25

Status:

Tags:알고리즘

너비 우선 탐색 BFS Breadth-First Search

• 시작 노드에서 인접한 모든 노드를 모두 방문하고, 인접한 노드들을 방문하는 탐색 알고리즘
• 큐(queue) 사용
• 방문 체크

작동 방식

1. 초기화:시작 노드를 큐에 넣고 방문 표시
2. 탐색: 큐가 빌때까지 반복
   1. 큐에서 노드 꺼내 현재 노드로 설정
   2. 현재 노드의 미방문 인접 노드들 모두 큐에 추가
   3. 추가된 노드들 방문 표시
3. 종료: 큐가 빌때까지 반복

구현 방식

1. 인접 리스트 이용

from collections import deque
def bfs_adjacency_list(graph, start):
    """
    시간복잡도: O(V + E) (V: 노드 수, E: 간선 수) 각 노드와 간선을 한 번씩 방문
    공간복잡도: O(V) (V: 노드 수)  방문 체크를 위한 추가 공간
    :param graph: 인접 리스트로 표현된 그래프
    :param start: 시작 노드
    :return: BFS 탐색 결과
    """
    visited = set()  # 방문한 노드를 저장하는 집합
    queue = deque([start])  # 시작 노드를 큐에 추가
    result = []  # BFS 탐색 결과를 저장할 리스트
 
    while queue:
        node = queue.popleft()  # 큐에서 노드를 꺼냄
        if node not in visited:  # 노드를 방문하지 않았다면
            visited.add(node)  # 노드를 방문 처리
            result.append(node)  # 결과에 추가
 
			# 미방문 인접 노드들을 큐에 추가
            for neighbor in graph[node]:  # 인접한 노드를 모두 방문
                if neighbor not in visited:  # 방문하지 않은 노드라면
                    queue.append(neighbor)  # 큐에 추가
    return result

2. 인접 행렬 이용

def bfs_adjacency_matrix(matrix, start):
    """
    시간복잡도: O(V^2) (V: 노드 수) 모든 정점 쌍을 확인해야 함
    공간복잡도: O(V) (V: 노드 수)
    :param matrix: 인접 행렬로 표현된 그래프
    :param start: 시작 노드
    :return: BFS 탐색 결과
    """
	n = len(matrix)  # 노드의 수
	visited = [False] * n  # 방문한 노드를 저장하는 리스트
	queue = deque([start])  # 시작 노드를 큐에 추가
	result = []  # BFS 탐색 결과를 저장할 리스트
 
	visited[start] = True  # 시작 노드를 방문 처리
	while queue:
		node = queue.popleft()  # 큐에서 노드를 꺼냄
		result.append(node)  # 결과에 추가
 
		for i in range(n):  # 인접 행렬을 순회
			if matrix[node][i] == 1 and not visited[i]:  # 인접하고 방문하지 않은 노드라면
				visited[i] = True  # 노드를 방문 처리
				queue.append(i)  # 큐에 추가
	return result
 

References

깊이 우선 탐색 큐

너비 우선 탐색 (BFS) 핸드북