Ch.7 그래프

BFS — 너비 우선 탐색, 최단거리의 열쇠

BFS의 동작 원리를 큐로 설명한다BFS가 최단거리를 보장하는 이유를 이해한다레벨별 탐색 패턴을 구현한다

물결이 퍼지듯 한 겹씩 탐색한다

연못에 돌을 던지면 물결이 동심원으로 퍼집니다. BFS도 마찬가지 — 시작점에서 거리 1인 노드 → 거리 2인 노드 → ... 순서로 탐색합니다.

DFS처럼 깊이 파고들면 안 될까? 왜 한 겹씩 탐색해야 하지?

한 겹씩 탐색하기 때문에 처음 도착한 경로가 곧 최단 경로입니다. 이것이 BFS의 핵심 강점입니다.

lightbulb

핵심 개념

BFS(너비 우선 탐색)

시작점에서 가까운 순서대로 탐색

레벨(Level)

시작점에서의 거리(엣지 수) 기준 층

article

핵심 내용

최단거리를 구하는 가장 확실한 무기, BFS

DFS는 스택(LIFO) → 깊이 우선 BFS는 큐(FIFO) → 너비 우선

"최단"이라는 키워드가 보이면 99% BFS입니다!

파이썬에서 BFS는 deque로 구현합니다

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    
    while queue:
        node = queue.popleft()   # FIFO — 가장 먼저 넣은 것
        print(node, end=' ')
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return visited

graph = {'A':['B','C'], 'B':['A','D'], 'C':['A','D'], 'D':['B','C']}
bfs(graph, 'A')  # A B C D

DFS vs BFS 코드 차이 딱 하나! DFS: `stack.pop()` — 마지막에 넣은 것 먼저 BFS: `queue.popleft()` — 먼저 넣은 것 먼저 나머지 구조는 완전히 동일합니다

면접관이 "list.pop(0)" 쓰면 감점합니다. O(n)이니까요. deque.popleft()는 O(1)!

BFS로 시작점에서 각 노드까지 최단 거리를 구합니다

from collections import deque

def shortest_distance(graph, start):
    dist = {start: 0}
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in dist:
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)
    
    return dist

graph = {0:[1,2], 1:[0,3], 2:[0,3], 3:[1,2,4], 4:[3]}
print(shortest_distance(graph, 0))
# {0:0, 1:1, 2:1, 3:2, 4:3}

`dist[neighbor] = dist[node] + 1` 이 한 줄이 BFS 최단거리의 전부입니다

BFS는 가중치가 동일한(=1) 그래프에서만 최단거리를 보장합니다. 가중치가 다르면 다익스트라를 써야 합니다

BFS가 레벨별로 탐색하는 과정을 추적합니다

Level 0: A → Level 1: B, C → Level 2: D 가까운 노드부터 처리됩니다

면접에서 "레벨별로"라는 키워드가 나오면 이 패턴!

def bfs_by_level(graph, start):
    visited = set([start])
    queue = deque([start])
    level = 0
    
    while queue:
        size = len(queue)           # 현재 레벨의 노드 수
        print(f'Level {level}:', end=' ')
        
        for _ in range(size):       # 현재 레벨만 처리
            node = queue.popleft()
            print(node, end=' ')
            for nb in graph[node]:
                if nb not in visited:
                    visited.add(nb)
                    queue.append(nb)
        
        print()
        level += 1

핵심은 `for _ in range(len(queue))`. 루프 시작 시점의 queue 크기만큼만 처리하면 한 레벨입니다

가중치가 없는 그래프에서 A→D 최단거리를 구하려면 어떤 알고리즘?

파이썬에서 BFS를 구현할 때 list.pop(0) 대신 deque.popleft()를 쓰는 이유는 시간 복잡도 때문이다

BFS 정복 완료!

key

핵심 용어

🌊

BFS

Breadth-First Search — 너비 우선 탐색

📦

큐(Queue)

FIFO — 먼저 넣은 것을 먼저 꺼냄

📏

최단 거리

가중치 없는 그래프에서 BFS = 최단 경로

edit_note

정리 노트

너비 우선 탐색 (BFS)

핵심 패턴

BFS 기본: `deque([start])` → `popleft()` → 이웃 append
최단 거리: `dist[nb] = dist[node] + 1`
레벨 탐색: `for _ in range(len(queue))`로 레벨 구분

DFS vs BFS

DFS: 스택/재귀 — 경로 탐색, 연결 요소
BFS: 큐 — 최단거리, 레벨별 탐색

★

'최단'이라는 키워드가 보이면 BFS! deque.popleft()는 필수!

image

시각 자료

다이어그램: ds-d55

check_circle

핵심 정리

1BFS = 큐(FIFO)로 가까운 순서대로 탐색
2가중치 없는 그래프에서 BFS = 최단거리
3deque.popleft() O(1) vs list.pop(0) O(n)

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작