BFS란?

1. BFS란?

그래프 혹은 트리에서 특정 시작점에서 가까운 정점부터 차례로 탐색하는 알고리즘. 탐색의 순차성 보장을 위해, 큐(Queue)의 선입선출(FIFO) 방식을 활용하여 구현한다.

from collections import deque

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

    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# 예시 그래프 (인접 리스트)
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}

bfs(graph, 'A')

2. BFS와 DFS의 비교

DFS는 깊이 탐색 알고리즘으로 한 경로를 끝까지 따라간 뒤, 더 이상 갈 수 없을 때 다시 돌아와서(Backtracking) 다른 경로를 탐색하는 알고리즘이다. 즉, 깊게 들어갔다가 다시 올라오는 방식으로 탐색한다.

구분	BFS	DFS
탐색 순서	가까운 노드부터	깊이 우선, 멀리 있는 노드부터
사용 자료구조	큐 (Queue)	스택(Stack) 혹은 재귀 호출
시간 복잡도	O(V + E)	O(V + E)
공간 복잡도	O(V) (큐 + 방문배열)	O(V) (스택 + 방문배열)
적합한 문제	최단 거리, 최단 단계 탐색 (ex.미로에서 출구까지의 최소 이동 횟수)	경로 존재 여부, 백트래킹 문제 등(ex.퍼즐 조합, 미로에서 가능한 모든 경로 탐색)

3. 그래프 형태에 따른 실제 수행 시간

BFS의 시간복잡도는 O(V + E) (V: 정점 수, E: 간선 수)이다.

• 그래프 형태에 따른 영향:

  • 희소그래프 (Sparse Graph): 간선 수가 정점 수에 비해 적음(보통 E = O(V) 수준으로 간선 수가 제한적인 경우) → BFS 수행 시간이 빠름
    ex) 트리(간선 수 = V - 1), 도로가 제한된 지도

  • 밀집 그래프 (Dense Graph): 노드 수에 비해 간선의 수가 훨씬 많음(최대 E ≈ V²)→ BFS 수행 시간이 느려짐
    ex) 완전 그래프, 모든 정점이 서로 연결된 네트워크