Python 알고리즘

Python의 너비 우선 탐색(BFS)

이 레슨에서는 너비 우선 탐색과 deque 큐로 그래프를 단계별로 탐색합니다.

  • 중급
  • 2분 분량
  • 실행 가능한 예제 1개

소개

어떤 문제를 해결하나요

소셜 네트워크에서 한 사람에게서 다른 사람까지 몇 단계를 거쳐야 할까요? 미로의 한 칸에서 출구까지는 몇 걸음일까요? 너비 우선 탐색은 가까운 곳부터 거리 순서대로 한 겹씩 넓혀 가며 탐색합니다. 그래서 어떤 노드에 처음 도착했을 때 지나온 길이 곧 최단 경로입니다.

일상 속 비유

너비 우선 탐색은 연못에 퍼지는 물결과 같습니다. 시작점에 돌을 떨어뜨리면 물결은 한 걸음 거리에 있는 모든 곳에 먼저 닿고, 그다음에 두 걸음 거리에 있는 모든 곳에 닿습니다. 가까운 곳에 모두 닿기 전에는 더 먼 곳으로 가지 않습니다.

연못의 물결에서 코드로
queue = deque(["A"])🪨 A에 돌 떨어뜨리기
node = queue.popleft()🌊 거리가 가까운 순서대로 다음 노드 꺼내기
if neighbor not in visited:🔎 아직 닿지 않은 곳인가요?
queue.append(neighbor)➕ 다음 물결에 추가하기
큐를 써서 가까운 노드부터 방문합니다.
한 문장으로

너비 우선 탐색(BFS)은 큐를 사용해서 시작 노드에서 가까운 단계부터 차례로 그래프를 방문합니다. 그래서 가중치가 없는 그래프에서 최단 경로를 찾을 수 있습니다.

핵심 포인트

  1. queue는 탐색을 기다리는 노드를 담습니다. 먼저 들어온 노드가 먼저 나옵니다.
  2. visited는 이미 발견한 노드를 기록합니다. 그래서 같은 노드가 두 번 들어가지 않고, 순환(사이클)이 있어도 끝없이 돌지 않습니다.
  3. node = queue.popleft()는 다음 노드를 꺼냅니다. 그 노드의 이웃 중 아직 방문하지 않은 것은 큐의 맨 뒤에 들어갑니다.
  4. order를 보면 A가 먼저 나오고, 그다음에 이웃인 B와 C, 그다음에 한 단계 더 먼 D와 E가 나옵니다.

언제 사용하나요?

  • 가중치 없는 그래프, 격자, 미로에서 최단 경로 찾기.
  • 소셜 네트워크에서 두 사람이 몇 단계 떨어져 있는지 구하기.
  • 웹 크롤러. 그리고 시작점에서 갈 수 있는 모든 곳 찾기.

필요 없는 경우

  • 도로의 거리처럼 간선마다 비용이 다른 경우: 다익스트라 알고리즘을 씁니다.
  • 백트래킹처럼 경로 하나를 끝까지 가 본 뒤에 다른 경로를 봐야 하는 경우: 깊이 우선 탐색을 씁니다.

Python의 너비 우선 탐색(BFS) 시각화

O(V + E)

재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.

예제 코드

코드 실행 →
main.py
from collections import deque

graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
queue = deque(["A"])
visited = {"A"}
order = []

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

print(order)
이 예제의 실행 버튼 만들기

실행 결과

['A', 'B', 'C', 'D', 'E']

코드 설명

큐 queue에는 방문을 기다리는 정점이 들어 있고, 들어온 순서대로 나옵니다. 집합 visited는 이미 만난 정점을 기억해서, 그래프에 사이클이 있어도 같은 정점을 여러 번 방문하지 않게 합니다. 방문 순서는 A, B, C, D, E이고, 복잡도는 O(V + E)입니다. 여기서 V는 정점 수, E는 간선 수입니다.

값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.

연습 문제

아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.

  1. 빈 리스트, 요소가 하나인 리스트, 중복이 있는 리스트로 테스트해 보세요.
  2. 단계마다 상태를 출력해서 알고리즘이 동작하는 모습을 살펴보세요.
  3. 요소 100개, 1,000개, 10,000개로 실행 시간을 재고 다른 방법과 비교해 보세요.
Python 컴파일러에서 실행 →

자주 하는 실수

방문 표시를 너무 늦게 하기

큐에서 꺼낼 때에야 방문 표시를 하면 같은 노드가 큐에 여러 번 들어갈 수 있습니다.

문제
node = queue.popleft()
visited.add(node)
for neighbor in graph[node]:
    if neighbor not in visited:
        queue.append(neighbor)
수정
for neighbor in graph[node]:
    if neighbor not in visited:
        visited.add(neighbor)
        queue.append(neighbor)

이 레슨을 마쳤나요?

학습 완료로 표시하면 진행 상황을 기록할 수 있습니다.

챌린지로 연습하기

이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.

모든 챌린지