이미지 로딩 중...
AI Generated
2025. 11. 7. · 3 Views
BFS 구현을 위한 큐 활용 완벽 가이드
BFS(너비 우선 탐색) 알고리즘에서 큐를 활용하는 방법을 초급 개발자도 쉽게 이해할 수 있도록 설명합니다. 실무에서 바로 활용할 수 있는 구체적인 코드 예제와 함께 큐의 역할, BFS의 동작 원리, 그리고 실전 팁을 제공합니다.
목차
- 큐의 기본 개념과 BFS에서의 역할
- 그래프 표현과 BFS 초기 설정
- BFS 메인 루프 구현
- 최단 거리 계산하기
- 레벨 순서 순회
- 최단 경로 역추적
- BFS로 미로 찾기 구현
- 다중 출발점 BFS
- BFS와 DFS 비교
- BFS 시간 복잡도 분석
1. 큐의 기본 개념과 BFS에서의 역할
시작하며
여러분이 소셜 네트워크에서 친구 추천 기능을 구현하거나, 미로 찾기 게임을 만들 때 이런 고민을 해본 적 있나요? "어떻게 하면 가장 가까운 친구부터 차례대로 찾을 수 있을까?" 또는 "미로의 최단 경로를 어떻게 찾을 수 있을까?" 이런 문제는 실제 개발 현장에서 자주 발생합니다.
네비게이션 앱의 최단 경로 찾기, 게임에서의 AI 이동, 네트워크 라우팅 등 우리가 사용하는 많은 서비스의 핵심에는 이러한 탐색 알고리즘이 숨어있습니다. 만약 잘못된 방법으로 탐색하면 불필요한 경로를 돌아가거나, 최단 거리를 찾지 못할 수 있습니다.
바로 이럴 때 필요한 것이 큐(Queue)를 활용한 BFS(너비 우선 탐색)입니다. 큐는 BFS의 핵심 도구로, 같은 거리에 있는 노드들을 레벨별로 순서대로 방문할 수 있게 해줍니다.
개요
간단히 말해서, 큐는 선입선출(FIFO: First In First Out) 구조의 자료구조입니다. 마치 은행 대기줄처럼, 먼저 들어온 사람이 먼저 나가는 방식이죠.
BFS에서 큐가 필요한 이유는 명확합니다. 그래프나 트리를 탐색할 때, 현재 노드에서 가까운 노드부터 차례대로 방문해야 하기 때문입니다.
예를 들어, 소셜 네트워크에서 직접 친구(1촌)를 모두 확인한 후, 그 다음에 친구의 친구(2촌)를 확인하는 방식으로 탐색해야 합니다. 기존에 스택을 사용하면 깊이 우선 탐색(DFS)이 되어버립니다.
하지만 큐를 사용하면 레벨 순서대로 탐색할 수 있어, 최단 거리를 보장받을 수 있습니다. 큐의 핵심 특징은 세 가지입니다.
첫째, enqueue(추가) 연산으로 큐의 뒤에 데이터를 넣습니다. 둘째, dequeue(제거) 연산으로 큐의 앞에서 데이터를 꺼냅니다.
셋째, 이 순서가 유지되기 때문에 BFS에서 방문 순서를 완벽하게 제어할 수 있습니다. 이러한 특징들이 BFS 알고리즘의 정확성과 효율성을 보장하는 핵심 요소입니다.
코드 예제
from collections import deque
# 큐 생성 - deque를 사용하면 O(1)의 성능을 보장합니다
queue = deque()
# enqueue: 큐에 데이터 추가
queue.append(1)
queue.append(2)
queue.append(3)
# dequeue: 큐에서 데이터 꺼내기 (먼저 들어온 것부터)
first = queue.popleft() # 1이 나옴
second = queue.popleft() # 2가 나옴
# 큐가 비어있는지 확인
if queue:
print(f"남은 데이터: {queue}") # deque([3])
설명
이것이 하는 일: 큐는 BFS 탐색에서 "다음에 방문할 노드들"을 저장하고 관리하는 역할을 합니다. 마치 할 일 목록처럼, 방문해야 할 노드들을 순서대로 보관했다가 하나씩 꺼내서 처리합니다.
첫 번째로, deque() 생성과 append() 메서드는 큐에 데이터를 추가하는 역할을 담당합니다. Python의 collections.deque는 일반 리스트보다 훨씬 효율적입니다.
왜냐하면 리스트의 pop(0)은 O(n)의 시간이 걸리지만, deque의 popleft()는 O(1)로 즉시 실행되기 때문입니다. 이는 수천, 수만 개의 노드를 탐색할 때 엄청난 성능 차이를 만듭니다.
그 다음으로, popleft() 메서드가 실행되면서 가장 먼저 들어온 데이터를 꺼냅니다. 이것이 BFS의 핵심입니다.
1, 2, 3 순서로 넣었다면, 반드시 1, 2, 3 순서로 나옵니다. 내부적으로 deque는 양방향 연결 리스트로 구현되어 있어, 앞뒤 모두에서 빠르게 데이터를 추가하고 제거할 수 있습니다.
마지막으로, 큐의 비어있음을 확인하는 것이 BFS 종료 조건을 결정합니다. if queue:로 확인하면, 더 이상 방문할 노드가 없을 때 탐색이 자연스럽게 종료됩니다.
이는 모든 도달 가능한 노드를 빠짐없이 방문했다는 의미입니다. 여러분이 이 코드를 사용하면 BFS 구현의 기초를 완벽하게 다질 수 있습니다.
실무에서는 이 큐 구조를 통해 최단 경로 찾기, 레벨별 노드 처리, 그리고 순차적 탐색이 필요한 모든 상황에 활용할 수 있습니다. 또한 메모리 효율성과 실행 속도를 동시에 확보할 수 있어, 대규모 그래프 탐색에서도 안정적으로 동작합니다.
실전 팁
💡 Python에서 큐를 구현할 때 절대 list의 pop(0)을 사용하지 마세요. 항상 collections.deque를 사용해야 O(1) 성능을 보장받을 수 있습니다. 큰 데이터에서는 100배 이상 속도 차이가 납니다.
💡 큐가 비어있는지 확인할 때 len(queue) == 0 보다는 if queue: 또는 if not queue: 방식이 더 파이썬스럽고 가독성도 좋습니다.
💡 디버깅할 때는 큐의 현재 상태를 출력해보세요. print(f"현재 큐: {list(queue)}")로 어떤 노드들이 대기 중인지 확인하면 BFS 동작을 이해하는 데 큰 도움이 됩니다.
💡 멀티스레드 환경에서는 queue.Queue()를 사용하세요. collections.deque는 thread-safe하지 않지만, queue.Queue()는 동시성을 보장합니다.
💡 메모리가 제한적인 환경이라면 큐에 들어갈 최대 크기를 deque(maxlen=1000)처럼 제한할 수 있습니다. 이는 메모리 오버플로우를 방지합니다.
2. 그래프 표현과 BFS 초기 설정
시작하며
여러분이 복잡한 도로망이나 네트워크 구조를 프로그램으로 표현해야 할 때, 어떻게 시작해야 할지 막막했던 경험이 있나요? "이 도시들의 연결 관계를 어떻게 코드로 옮기지?"라는 고민은 모든 개발자가 한 번쯤 겪는 문제입니다.
이런 문제는 실제 개발 현장에서 매우 흔합니다. 지도 서비스, 추천 시스템, 의존성 관리 등 수많은 시스템이 그래프 구조로 데이터를 표현합니다.
잘못된 표현 방식을 선택하면 나중에 탐색 알고리즘을 구현할 때 불필요하게 복잡해지거나, 성능이 크게 저하될 수 있습니다. 바로 이럴 때 필요한 것이 인접 리스트를 사용한 그래프 표현과 BFS 초기 설정입니다.
이 방법은 그래프의 연결 관계를 효율적으로 저장하고, BFS를 시작할 수 있는 완벽한 기반을 제공합니다.
개요
간단히 말해서, 그래프는 노드(정점)와 간선(엣지)으로 이루어진 자료구조이며, 인접 리스트는 각 노드가 연결된 노드들의 목록을 딕셔너리나 리스트로 표현하는 방식입니다. 인접 리스트가 필요한 이유는 공간 효율성과 탐색 효율성 때문입니다.
예를 들어, 소셜 네트워크에서 수백만 명의 사용자가 있지만 각 사용자는 평균 수백 명의 친구만 갖는 경우(희소 그래프), 인접 행렬을 사용하면 대부분의 공간이 낭비됩니다. 반면 인접 리스트는 실제 연결된 관계만 저장하므로 메모리를 효율적으로 사용합니다.
기존에 2차원 배열(인접 행렬)로 표현했다면 O(V²)의 공간이 필요했습니다. 하지만 인접 리스트를 사용하면 O(V+E)의 공간만 필요하며, 특정 노드의 이웃을 찾을 때도 훨씬 빠릅니다.
인접 리스트의 핵심 특징은 세 가지입니다. 첫째, 딕셔너리 형태로 {노드: [연결된 노드들]} 구조를 갖습니다.
둘째, 특정 노드의 이웃을 O(1)에 접근할 수 있습니다. 셋째, BFS 구현 시 이웃 노드들을 바로 큐에 넣을 수 있어 매우 직관적입니다.
이러한 특징들이 BFS 알고리즘을 간결하고 효율적으로 만들어줍니다.
코드 예제
# 그래프를 인접 리스트로 표현 - 딕셔너리 사용
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# BFS 초기 설정
from collections import deque
start_node = 'A'
visited = set() # 방문한 노드를 기록 - O(1) 조회 성능
queue = deque([start_node]) # 시작 노드를 큐에 추가
visited.add(start_node) # 시작 노드를 방문 처리
print(f"BFS 시작 준비 완료. 시작 노드: {start_node}")
설명
이것이 하는 일: 그래프의 연결 관계를 메모리 효율적으로 저장하고, BFS 탐색을 시작하기 위한 초기 상태를 설정합니다. 마치 여행을 떠나기 전에 지도를 펼치고 출발점을 표시하는 것과 같습니다.
첫 번째로, 딕셔너리로 구현한 그래프는 각 노드를 키로, 연결된 노드들의 리스트를 값으로 저장합니다. 예를 들어, 'A'는 'B'와 'C'와 연결되어 있다는 정보를 'A': ['B', 'C']로 명확하게 표현합니다.
이 방식은 실제 도로망, 친구 관계, 웹 페이지 링크 등 어떤 관계도 직관적으로 표현할 수 있습니다. 무방향 그래프라면 양쪽에 모두 추가해야 하고, 방향 그래프라면 한쪽만 추가하면 됩니다.
그 다음으로, visited = set()으로 방문 기록을 관리합니다. 왜 리스트가 아닌 set을 사용할까요?
set은 in 연산이 O(1)이지만 리스트는 O(n)이기 때문입니다. BFS에서는 "이 노드를 이미 방문했는가?"를 수천 번 확인하게 되므로, 이 차이가 전체 성능을 크게 좌우합니다.
또한 set은 중복을 자동으로 방지하므로 같은 노드를 두 번 방문하는 실수를 원천적으로 차단합니다. 세 번째로, 시작 노드를 큐에 넣고 동시에 방문 처리합니다.
이것이 매우 중요한 포인트입니다. 많은 초보자들이 큐에서 꺼낼 때 방문 처리를 하는데, 그러면 같은 노드가 큐에 여러 번 들어가서 중복 처리가 발생합니다.
큐에 넣는 순간 방문 처리를 해야 이러한 중복을 막을 수 있습니다. 마지막으로, 이 초기 설정이 완료되면 BFS의 메인 루프를 시작할 준비가 끝납니다.
큐에는 탐색할 첫 번째 노드가 들어있고, visited에는 이미 방문한 노드가 기록되어 있으며, graph에는 전체 연결 관계가 담겨있습니다. 여러분이 이 구조를 사용하면 어떤 복잡한 그래프도 명확하게 표현할 수 있습니다.
실무에서는 데이터베이스에서 읽어온 관계 데이터를 이 형태로 변환하거나, JSON 형태의 네트워크 데이터를 파싱하여 이 구조로 만듭니다. 또한 가중치가 있는 그래프라면 'A': [('B', 5), ('C', 3)] 형태로 확장할 수도 있어, 다익스트라 알고리즘 등 고급 알고리즘으로도 쉽게 발전시킬 수 있습니다.
실전 팁
💡 그래프를 만들 때 defaultdict를 사용하면 더 편리합니다. from collections import defaultdict; graph = defaultdict(list)로 선언하면, 존재하지 않는 키에 접근해도 자동으로 빈 리스트가 생성됩니다.
💡 무방향 그래프를 만들 때는 양방향으로 간선을 추가해야 합니다. A-B 연결이라면 graph['A'].append('B')와 graph['B'].append('A') 둘 다 필요합니다. 이를 잊으면 한쪽 방향으로만 탐색됩니다.
💡 visited를 set 대신 딕셔너리로 사용하면 추가 정보를 저장할 수 있습니다. 예: visited = {'A': 0}처럼 노드와 함께 거리를 저장하면 최단 거리를 동시에 계산할 수 있습니다.
💡 대규모 그래프에서는 메모리를 아끼기 위해 visited를 비트셋이나 불린 배열로 구현할 수도 있습니다. 노드가 숫자로 표현되는 경우 visited = [False] * n이 set보다 빠를 수 있습니다.
💡 그래프 데이터를 외부에서 읽어올 때는 간선 리스트 형태 [(A,B), (B,C), ...]를 인접 리스트로 변환하는 함수를 미리 만들어두면 재사용하기 좋습니다.
3. BFS 메인 루프 구현
시작하며
여러분이 미로를 탐색하는 로봇을 프로그래밍한다고 상상해보세요. 로봇이 "다음에 어디로 가야 하지?"라고 계속 물어본다면, 여러분은 어떤 규칙을 제시하시겠습니까?
그냥 아무 곳이나 가라고 할까요, 아니면 체계적인 순서를 정해줄까요? 이런 문제는 게임 AI, 경로 찾기, 퍼즐 풀이 등 실제 개발에서 핵심적인 부분입니다.
무작위로 탐색하면 같은 곳을 여러 번 방문하거나, 가까운 목적지를 놓치고 먼 곳을 헤맬 수 있습니다. 체계적이지 않은 탐색은 비효율적이고 예측 불가능한 결과를 만듭니다.
바로 이럴 때 필요한 것이 BFS의 메인 루프입니다. 이 루프는 큐가 빌 때까지 반복하면서, 각 노드를 방문하고 이웃 노드들을 체계적으로 큐에 추가하는 방식으로 완벽한 탐색을 보장합니다.
개요
간단히 말해서, BFS 메인 루프는 "큐에서 하나 꺼내기 → 처리하기 → 이웃 노드들을 큐에 추가하기"를 반복하는 구조입니다. 이 간단한 패턴이 모든 BFS의 핵심입니다.
이 루프가 필요한 이유는 그래프의 모든 도달 가능한 노드를 빠짐없이, 그리고 레벨 순서대로 방문하기 위함입니다. 예를 들어, 소셜 네트워크에서 친구 추천을 할 때, 1촌을 모두 확인한 후 2촌을 확인하고, 그 다음 3촌을 확인하는 식으로 거리 순서가 자동으로 보장됩니다.
이는 큐의 FIFO 특성 덕분입니다. 기존에 재귀로 탐색했다면 스택 오버플로우 위험이 있고 깊이가 깊어질수록 메모리 소비가 증가합니다.
하지만 반복문과 큐를 사용하면 메모리를 효율적으로 관리하면서 무한히 깊은 그래프도 안전하게 탐색할 수 있습니다. BFS 메인 루프의 핵심 특징은 세 가지입니다.
첫째, while queue: 조건으로 더 이상 방문할 노드가 없을 때 자동으로 종료됩니다. 둘째, popleft()로 큐에서 노드를 꺼내는 순서가 곧 방문 순서가 됩니다.
셋째, 이웃 노드를 큐에 추가할 때 방문 체크를 하여 중복 방문을 완벽하게 방지합니다. 이러한 특징들이 BFS를 안정적이고 효율적인 알고리즘으로 만듭니다.
코드 예제
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
result = [] # 방문 순서를 기록
# 큐가 빌 때까지 반복 - 모든 도달 가능한 노드 탐색
while queue:
node = queue.popleft() # 큐에서 노드 꺼내기
result.append(node) # 방문 처리
# 현재 노드의 모든 이웃 확인
for neighbor in graph[node]:
if neighbor not in visited: # 아직 방문하지 않은 노드만
visited.add(neighbor) # 방문 표시
queue.append(neighbor) # 큐에 추가
return result
설명
이것이 하는 일: BFS 메인 루프는 그래프의 모든 도달 가능한 노드를 레벨 순서대로 방문하고, 각 노드에서 수행할 작업을 처리합니다. 마치 파도가 퍼져나가듯이, 시작점에서 가까운 노드부터 차례대로 탐색합니다.
첫 번째로, while queue: 루프는 큐에 노드가 남아있는 동안 계속 실행됩니다. 처음에는 시작 노드 하나만 있지만, 루프를 돌면서 이웃 노드들이 계속 추가됩니다.
모든 도달 가능한 노드를 방문하고 나면 큐가 자연스럽게 비어서 루프가 종료됩니다. 이는 탐색이 완료되었다는 확실한 신호입니다.
그 다음으로, node = queue.popleft()가 실행되면서 큐의 맨 앞 노드를 꺼냅니다. 이 노드가 바로 지금 처리할 대상입니다.
큐의 FIFO 특성 덕분에, 먼저 발견된 노드(더 가까운 노드)가 먼저 처리됩니다. 이것이 BFS가 최단 경로를 보장하는 핵심 원리입니다.
만약 여기서 pop()을 사용했다면 DFS처럼 동작하게 됩니다. 세 번째로, for neighbor in graph[node]: 루프에서 현재 노드의 모든 이웃을 확인합니다.
그래프의 인접 리스트 구조 덕분에, 이 노드와 연결된 모든 노드를 O(1)에 가져올 수 있습니다. 각 이웃에 대해 if neighbor not in visited: 조건으로 아직 방문하지 않은 노드만 선별합니다.
set의 in 연산은 O(1)이므로 이 체크는 매우 빠릅니다. 마지막으로, 미방문 노드를 발견하면 즉시 visited에 추가하고 큐에 넣습니다.
이 순서가 매우 중요합니다! 큐에 넣은 후 visited에 추가하면, 같은 노드가 여러 경로에서 발견될 때 큐에 중복으로 들어갑니다.
하지만 큐에 넣기 전에 visited에 추가하면 이런 중복이 원천 차단됩니다. 이것이 BFS의 시간 복잡도를 O(V+E)로 유지하는 핵심 기법입니다.
여러분이 이 코드를 사용하면 어떤 그래프든 체계적으로 탐색할 수 있습니다. 실무에서는 이 기본 구조를 바탕으로 다양한 기능을 추가합니다.
예를 들어, 특정 노드를 찾으면 즉시 리턴하거나, 각 노드까지의 거리를 계산하거나, 경로를 역추적하는 등의 작업을 할 수 있습니다. 또한 이 패턴을 익혀두면 다익스트라, A* 같은 고급 알고리즘도 쉽게 이해할 수 있습니다.
실전 팁
💡 큐에 넣을 때 방문 표시를 하세요. 큐에서 꺼낼 때 방문 표시를 하면 같은 노드가 큐에 여러 번 들어가서 시간과 메모리가 낭비됩니다. 이는 매우 흔한 실수입니다.
💡 특정 목표 노드를 찾는 경우, 찾자마자 return하면 불필요한 탐색을 줄일 수 있습니다. if node == target: return True 같은 조건을 추가하세요.
💡 디버깅 시 각 단계에서 print(f"방문: {node}, 큐: {list(queue)}")를 출력하면 BFS가 어떻게 진행되는지 시각적으로 이해할 수 있습니다.
💡 그래프가 끊어져 있을 수 있다면(disconnected graph), 모든 노드를 시작점으로 한 번씩 BFS를 실행해야 합니다. for node in graph: if node not in visited: bfs(graph, node) 패턴을 사용하세요.
💡 큰 그래프에서는 방문 순서를 리스트에 모두 저장하지 말고, 필요한 정보만 수집하세요. result.append(node) 대신 카운트만 증가시키거나, 조건에 맞는 노드만 저장하면 메모리를 아낄 수 있습니다.
4. 최단 거리 계산하기
시작하며
여러분이 배달 앱을 개발하는데, "고객까지 최소 몇 번의 경유지를 거쳐야 하는가?"를 계산해야 한다면 어떻게 하시겠습니까? 단순히 노드를 방문하는 것만으로는 부족합니다.
각 노드까지의 거리 정보가 필요합니다. 이런 문제는 게임에서의 이동 횟수 계산, 네트워크의 홉 수 측정, 친구 관계의 촌수 계산 등 실무에서 매우 자주 발생합니다.
거리 정보 없이 탐색만 하면 "도달 가능한가?"는 알 수 있지만 "얼마나 가까운가?"는 알 수 없습니다. 이는 많은 애플리케이션에서 핵심적인 정보입니다.
바로 이럴 때 필요한 것이 거리 정보를 함께 관리하는 BFS입니다. 큐에 노드만 넣는 것이 아니라 (노드, 거리) 튜플을 넣거나, 별도의 거리 딕셔너리를 관리하여 각 노드까지의 최단 거리를 정확하게 추적합니다.
개요
간단히 말해서, 최단 거리 계산은 BFS의 기본 구조에 거리 추적 기능을 추가한 것입니다. 시작 노드는 거리 0이고, 각 이웃 노드는 현재 노드의 거리 + 1이 됩니다.
최단 거리 계산이 필요한 이유는 BFS가 레벨 순서로 탐색하기 때문에, 처음 발견한 경로가 자동으로 최단 경로가 되기 때문입니다. 예를 들어, A에서 E로 가는 경로가 A→B→E와 A→C→D→E 두 가지라면, BFS는 거리 2인 경로를 먼저 발견하고, 거리 3인 경로는 이미 방문 표시가 되어 있어 무시됩니다.
기존에 모든 경로를 탐색하고 비교하는 방법은 O(V!)의 시간이 걸릴 수 있습니다. 하지만 BFS는 각 노드를 한 번씩만 방문하므로 O(V+E)로 모든 노드까지의 최단 거리를 계산할 수 있습니다.
거리 계산의 핵심 특징은 세 가지입니다. 첫째, 딕셔너리나 튜플로 거리 정보를 함께 저장합니다.
둘째, 노드를 처음 발견했을 때의 거리가 곧 최단 거리입니다. 셋째, 가중치가 없는 그래프에서는 BFS가 다익스트라보다 간단하면서도 정확합니다.
이러한 특징들이 BFS를 최단 거리 문제의 완벽한 솔루션으로 만듭니다.
코드 예제
from collections import deque
def bfs_distance(graph, start):
visited = set([start])
queue = deque([(start, 0)]) # (노드, 거리) 튜플로 저장
distances = {start: 0} # 각 노드까지의 최단 거리
while queue:
node, dist = queue.popleft() # 노드와 거리를 함께 꺼냄
# 현재 노드의 모든 이웃 확인
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
new_dist = dist + 1 # 거리는 1씩 증가
distances[neighbor] = new_dist # 최단 거리 기록
queue.append((neighbor, new_dist)) # 큐에 추가
return distances # {노드: 최단거리} 딕셔너리 반환
설명
이것이 하는 일: 시작 노드에서 모든 도달 가능한 노드까지의 최단 거리를 계산합니다. BFS의 레벨 순서 탐색 특성을 활용하여, 처음 도달한 경로가 자동으로 최단 경로가 되도록 보장합니다.
첫 번째로, queue = deque([(start, 0)])에서 시작 노드와 거리 0을 튜플로 묶어 큐에 넣습니다. 이렇게 하면 큐에서 꺼낼 때 노드와 거리 정보를 동시에 얻을 수 있습니다.
distances = {start: 0}는 별도의 딕셔너리로 각 노드의 최단 거리를 저장합니다. 이 두 가지 방식 모두 유용하며, 상황에 따라 선택할 수 있습니다.
그 다음으로, node, dist = queue.popleft()에서 튜플 언패킹을 통해 노드와 현재까지의 거리를 동시에 가져옵니다. 이 dist 값이 시작 노드부터 현재 노드까지의 최단 거리입니다.
왜 최단인지 확신할 수 있을까요? BFS는 거리 0인 노드부터 처리하고, 그 다음 거리 1, 거리 2 순서로 처리하기 때문에, 더 짧은 경로가 있었다면 이미 방문 표시가 되어 있을 것이기 때문입니다.
세 번째로, new_dist = dist + 1로 이웃 노드의 거리를 계산합니다. 가중치가 없는 그래프에서는 간선의 길이가 모두 1이므로, 단순히 1을 더하면 됩니다.
이 값을 distances[neighbor] = new_dist로 저장하고, 동시에 (neighbor, new_dist) 튜플을 큐에 넣습니다. 이렇게 하면 다음 단계에서 이 노드를 처리할 때 올바른 거리 정보를 사용할 수 있습니다.
마지막으로, 함수는 distances 딕셔너리를 반환합니다. 이 딕셔너리는 시작 노드에서 각 노드까지의 최단 거리를 담고 있습니다.
예를 들어, {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2}처럼 결과가 나옵니다. 도달할 수 없는 노드는 딕셔너리에 포함되지 않으므로, 특정 노드의 거리를 확인할 때는 distances.get(node, float('inf'))처럼 기본값을 설정하는 것이 안전합니다.
여러분이 이 코드를 사용하면 복잡한 네트워크에서도 최단 경로를 빠르게 계산할 수 있습니다. 실무에서는 이를 바탕으로 "K번 이내에 도달 가능한 노드 찾기", "가장 먼 노드 찾기", "특정 거리에 있는 모든 노드 찾기" 같은 다양한 문제를 해결할 수 있습니다.
또한 이 패턴을 가중치가 있는 그래프로 확장하면 다익스트라 알고리즘의 기초가 됩니다.
실전 팁
💡 거리 정보를 튜플로 큐에 넣는 방식과 별도 딕셔너리로 관리하는 방식 모두 유효합니다. 튜플 방식이 더 명시적이고 이해하기 쉬우며, 딕셔너리 방식은 메모리를 약간 절약할 수 있습니다.
💡 특정 거리의 노드들만 찾으려면 if new_dist == target_distance: result.append(neighbor) 조건을 추가하세요. K번째 레벨의 모든 노드를 찾는 문제에서 유용합니다.
💡 최대 거리를 제한하고 싶다면 if new_dist > max_dist: continue를 추가하세요. 불필요하게 먼 노드까지 탐색하지 않아 성능이 향상됩니다.
💡 가중치가 있는 그래프라면 BFS 대신 다익스트라를 사용해야 합니다. BFS는 모든 간선의 가중치가 동일할 때만 최단 거리를 보장합니다.
💡 역방향 경로를 추적하려면 parent = {start: None}을 추가하고, 이웃을 발견할 때 parent[neighbor] = node로 부모를 기록하세요. 나중에 parent를 역추적하면 실제 경로를 복원할 수 있습니다.
5. 레벨 순서 순회
시작하며
여러분이 조직도를 레벨별로 출력하거나, 게임에서 "한 턴에 이동 가능한 모든 위치"를 표시해야 한다면 어떻게 하시겠습니까? 단순히 순서대로 방문하는 것이 아니라, "같은 레벨에 있는 노드들"을 그룹으로 묶어야 하는 상황입니다.
이런 문제는 트리 구조 시각화, 게임의 턴 기반 이동, 소셜 네트워크의 촌수별 친구 목록 등에서 필수적입니다. 일반 BFS로는 방문 순서는 알 수 있지만, 어떤 노드들이 같은 레벨인지 구분하기 어렵습니다.
레벨 정보가 없으면 "1촌 친구는 누구고, 2촌 친구는 누구인가?"를 명확하게 분리할 수 없습니다. 바로 이럴 때 필요한 것이 레벨 순서 순회(Level Order Traversal)입니다.
큐의 크기를 측정하여 한 레벨의 모든 노드를 처리한 후 다음 레벨로 넘어가는 방식으로, 레벨별로 완벽하게 그룹화할 수 있습니다.
개요
간단히 말해서, 레벨 순서 순회는 BFS를 실행하되 각 레벨의 노드들을 별도의 리스트로 묶어서 반환하는 방식입니다. [[레벨0 노드들], [레벨1 노드들], [레벨2 노드들], ...] 형태의 2차원 리스트가 결과입니다.
레벨 순서 순회가 필요한 이유는 시각화, 레벨별 통계, 단계적 처리 등에서 같은 깊이의 노드들을 하나의 그룹으로 다뤄야 하기 때문입니다. 예를 들어, 회사 조직도를 출력할 때 CEO(레벨 0), 임원진(레벨 1), 팀장(레벨 2), 팀원(레벨 3)처럼 계층별로 표시하려면 레벨 정보가 필수입니다.
기존에 각 노드에 레벨 정보를 태깅하는 방식도 가능하지만, 큐의 크기를 활용하는 방법이 더 직관적이고 간결합니다. 왜냐하면 큐에 있는 노드 수가 곧 현재 레벨의 노드 수이기 때문입니다.
레벨 순서 순회의 핵심 특징은 세 가지입니다. 첫째, 각 레벨을 처리하기 전에 level_size = len(queue)로 현재 레벨의 노드 수를 기록합니다.
둘째, 정확히 level_size번만큼 노드를 꺼내서 처리합니다. 셋째, 한 레벨의 모든 노드를 처리한 후 다음 레벨로 자동으로 넘어갑니다.
이러한 특징들이 레벨별 그룹화를 완벽하게 수행합니다.
코드 예제
from collections import deque
def bfs_level_order(graph, start):
visited = set([start])
queue = deque([start])
result = [] # 레벨별 노드들을 저장할 2차원 리스트
while queue:
level_size = len(queue) # 현재 레벨의 노드 개수
current_level = [] # 현재 레벨의 노드들
# 현재 레벨의 모든 노드 처리
for _ in range(level_size):
node = queue.popleft()
current_level.append(node)
# 이웃 노드들은 다음 레벨에 추가됨
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
result.append(current_level) # 현재 레벨을 결과에 추가
return result # [[레벨0], [레벨1], [레벨2], ...]
설명
이것이 하는 일: 그래프를 레벨별로 순회하여, 같은 거리에 있는 노드들을 하나의 그룹으로 묶습니다. 시작 노드는 레벨 0, 그 직접 이웃들은 레벨 1, 그 이웃의 이웃들은 레벨 2가 됩니다.
첫 번째로, level_size = len(queue)가 핵심 아이디어입니다. 외부 while 루프를 시작할 때 큐에 있는 노드들은 모두 같은 레벨입니다.
왜냐하면 이전 레벨의 모든 노드를 처리하면서 추가한 노드들이기 때문입니다. 예를 들어, 처음에는 시작 노드 1개(레벨 0), 그 다음에는 시작 노드의 이웃들(레벨 1), 그 다음에는 레벨 1 노드들의 이웃들(레벨 2)이 큐에 들어있게 됩니다.
그 다음으로, for _ in range(level_size): 루프가 정확히 현재 레벨의 노드 개수만큼만 반복합니다. 이것이 매우 중요합니다!
루프 안에서 새로운 노드들이 큐에 추가되지만, level_size는 루프 시작 전에 고정된 값이므로 영향을 받지 않습니다. 만약 while queue:를 사용했다면 새로 추가된 노드들까지 처리하게 되어 레벨 구분이 깨집니다.
세 번째로, 각 노드를 처리할 때 current_level.append(node)로 현재 레벨의 리스트에 추가합니다. 동시에 이웃 노드들은 큐에 추가되지만 current_level에는 추가되지 않습니다.
이 이웃들은 다음 외부 루프 반복에서 새로운 레벨로 처리됩니다. 이렇게 해서 레벨 간 명확한 경계가 유지됩니다.
마지막으로, 내부 for 루프가 끝나면 result.append(current_level)로 현재 레벨 전체를 결과에 추가합니다. 이제 큐에는 다음 레벨의 노드들만 남아있고, 외부 while 루프가 다시 시작되면서 다음 레벨을 처리합니다.
이 과정이 큐가 빌 때까지 반복되면서 모든 레벨이 순서대로 처리됩니다. 여러분이 이 코드를 사용하면 트리나 그래프의 계층 구조를 시각적으로 이해하고 표현할 수 있습니다.
실무에서는 "각 레벨의 노드 개수 세기", "특정 레벨만 추출하기", "레벨별 평균값 계산하기" 같은 작업에 활용됩니다. 또한 이진 트리의 레벨 순서 순회 문제(LeetCode 102번)의 정답 패턴이기도 하며, 많은 인터뷰 문제의 기초가 됩니다.
실전 팁
💡 level_size를 루프 밖에서 미리 계산하는 것이 핵심입니다. 루프 안에서 len(queue)를 호출하면 레벨 구분이 깨집니다.
💡 특정 레벨만 필요하다면 레벨 카운터를 추가하세요. level = 0으로 시작해서 외부 루프마다 level += 1하고, if level == target_level: return current_level로 조기 종료할 수 있습니다.
💡 각 레벨을 역순으로 출력하려면 current_level.reverse() 또는 result.append(current_level[::-1])을 사용하세요. 지그재그 레벨 순회 문제에서 유용합니다.
💡 레벨별 통계(최댓값, 평균 등)를 계산할 때는 current_level 리스트 전체를 저장하지 말고 바로 계산하세요. 메모리를 절약할 수 있습니다.
💡 이진 트리에서는 각 레벨의 맨 오른쪽 노드를 찾는 문제가 자주 나옵니다. current_level[-1]이 각 레벨의 마지막 노드입니다.
6. 최단 경로 역추적
시작하며
여러분이 내비게이션 앱을 만드는데, "최단 거리가 5km입니다"라고만 알려준다면 사용자가 만족할까요? 당연히 아닙니다.
"어떤 길을 통해 가야 하는지" 구체적인 경로를 보여줘야 합니다. 이런 문제는 게임의 경로 찾기, 물류 시스템의 배송 경로, 네트워크 패킷 라우팅 등 실제 개발에서 매우 흔합니다.
최단 거리만 계산하고 경로를 제공하지 않으면 사용자는 "어떻게 가야 하지?"라고 다시 물어야 합니다. 거리 정보 없이 경로 정보가 있어야 실질적인 가치가 있습니다.
바로 이럴 때 필요한 것이 부모 노드 추적(Parent Tracking)을 활용한 경로 역추적입니다. BFS를 실행하면서 각 노드를 어디서 왔는지 기록해두면, 목표 지점에서 출발점까지 거슬러 올라가며 전체 경로를 복원할 수 있습니다.
개요
간단히 말해서, 경로 역추적은 각 노드가 어느 노드로부터 발견되었는지를 parent 딕셔너리에 기록하고, 목표 노드에서 시작해서 parent를 계속 따라가며 경로를 재구성하는 방식입니다. 경로 역추적이 필요한 이유는 BFS가 최단 거리를 찾더라도 그 경로 자체는 저장하지 않기 때문입니다.
예를 들어, A에서 E까지 거리가 3이라는 것을 알았지만, A→B→D→E인지 A→C→D→E인지는 모릅니다. parent를 추적하면 이 정보를 효율적으로 복원할 수 있습니다.
기존에 모든 경로를 큐에 저장하는 방식은 메모리를 엄청나게 소비합니다. 각 노드마다 전체 경로 리스트를 복사하면 O(V²) 이상의 메모리가 필요할 수 있습니다.
하지만 parent 딕셔너리는 각 노드당 하나의 부모만 저장하므로 O(V)의 메모리로 충분합니다. 경로 역추적의 핵심 특징은 세 가지입니다.
첫째, parent[자식] = 부모 형태로 발견 관계를 기록합니다. 둘째, 목표 노드에서 parent를 계속 따라가면 시작 노드에 도달합니다.
셋째, 이 과정을 역순으로 뒤집으면 시작→목표의 실제 경로가 됩니다. 이러한 특징들이 메모리 효율적이면서도 완벽한 경로 복원을 가능하게 합니다.
코드 예제
from collections import deque
def bfs_shortest_path(graph, start, goal):
visited = set([start])
queue = deque([start])
parent = {start: None} # 각 노드의 부모 노드 기록
while queue:
node = queue.popleft()
# 목표 노드를 찾으면 경로 재구성
if node == goal:
path = []
current = goal
# 역추적: goal에서 start까지 거슬러 올라감
while current is not None:
path.append(current)
current = parent[current]
return path[::-1] # 역순으로 뒤집어서 start→goal 경로 반환
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
parent[neighbor] = node # 부모 기록
queue.append(neighbor)
return None # 경로가 없음
설명
이것이 하는 일: BFS로 최단 경로를 찾으면서, 각 노드가 어디서 왔는지 추적하여 실제 경로를 구체적으로 복원합니다. 마치 실타래를 풀듯이, 목표 지점에서 출발점까지 발자취를 역으로 따라갑니다.
첫 번째로, parent = {start: None}으로 부모 추적을 초기화합니다. 시작 노드는 부모가 없으므로 None으로 설정합니다.
이후 parent[neighbor] = node로 새로운 노드를 발견할 때마다 "이 노드는 어디서 왔는가"를 기록합니다. 예를 들어, B를 A에서 발견했다면 parent['B'] = 'A'가 됩니다.
이는 나중에 B의 이전 노드가 A임을 알려주는 빵가루 조각과 같습니다. 그 다음으로, if node == goal:에서 목표 노드를 발견하면 즉시 경로 재구성을 시작합니다.
더 이상 탐색할 필요가 없기 때문입니다. BFS의 특성상 처음 목표에 도달한 경로가 최단 경로이므로, 이 시점에서 바로 리턴해도 안전합니다.
이는 불필요한 탐색을 줄여 성능을 향상시킵니다. 세 번째로, while current is not None: 루프가 역추적을 수행합니다.
goal에서 시작해서 parent[goal]을 확인하고, 그 결과를 current로 삼아 다시 parent[current]를 확인하는 과정을 반복합니다. 시작 노드의 부모는 None이므로, 시작 노드에 도달하면 루프가 자연스럽게 종료됩니다.
예를 들어, E→D→B→A 순서로 거슬러 올라가면서 path 리스트에 추가됩니다. 마지막으로, return path[::-1]로 경로를 역순으로 뒤집습니다.
역추적 과정에서 goal→start 순서로 경로를 만들었기 때문에, 이를 뒤집으면 start→goal의 실제 경로가 됩니다. [::-1]은 파이썬에서 리스트를 역순으로 만드는 간결한 슬라이싱 문법입니다.
또는 path.reverse()를 사용해도 됩니다. 여러분이 이 코드를 사용하면 단순히 거리뿐 아니라 실제로 어떻게 이동해야 하는지를 제공할 수 있습니다.
실무에서는 이를 바탕으로 "경로 시각화", "중간 경유지 표시", "여러 경로 비교" 같은 기능을 구현합니다. 또한 미로 찾기, 게임 AI의 이동 경로, 네트워크 라우팅 테이블 등 다양한 곳에 활용됩니다.
parent 딕셔너리는 트리 구조를 표현하는 효율적인 방법이기도 해서, 다른 알고리즘에서도 자주 사용되는 패턴입니다.
실전 팁
💡 목표를 찾자마자 return하세요. 모든 노드를 탐색할 필요가 없습니다. 이는 성능을 크게 향상시킵니다.
💡 경로가 없을 때를 대비해 None을 반환하세요. 그래프가 disconnected이거나 목표에 도달할 수 없는 경우를 처리해야 합니다.
💡 여러 목표 중 하나를 찾는 경우, if node in goals: 형태로 확장할 수 있습니다. 가장 가까운 목표를 찾는 문제에 유용합니다.
💡 경로의 길이만 필요하다면 parent 대신 distance 딕셔너리만 사용하세요. 메모리를 절약할 수 있습니다.
💡 양방향 BFS를 구현하면 더 빠릅니다. 시작과 목표에서 동시에 탐색을 시작하여 중간에서 만나면 경로를 합칩니다. 큰 그래프에서는 2배 이상 빠를 수 있습니다.
7. BFS로 미로 찾기 구현
시작하며
여러분이 로봇 청소기의 경로 찾기 알고리즘을 개발하거나, 게임에서 캐릭터가 장애물을 피해 목표 지점에 도달하는 기능을 만든다면 어떻게 시작하시겠습니까? 추상적인 그래프가 아니라 실제 2차원 격자에서 동작하는 코드가 필요합니다.
이런 문제는 게임 개발, 로봇 공학, 경로 계획 등에서 매우 흔하게 발생합니다. 이론적인 그래프 알고리즘을 알고 있어도, 이를 실제 격자 맵에 적용하는 방법을 모르면 실무에서 활용할 수 없습니다.
특히 상하좌우 이동, 벽 충돌 체크, 경계 검사 등 구체적인 구현 디테일이 중요합니다. 바로 이럴 때 필요한 것이 2차원 격자에서의 BFS 구현입니다.
노드를 (행, 열) 좌표로 표현하고, 인접 노드를 상하좌우 4방향으로 정의하며, 벽과 경계를 체크하는 완전한 미로 찾기 알고리즘입니다.
개요
간단히 말해서, 미로 찾기는 2차원 배열에서 시작 좌표부터 목표 좌표까지의 최단 경로를 BFS로 찾는 것입니다. 0은 이동 가능한 칸, 1은 벽으로 표현하며, 상하좌우 4방향으로 이동합니다.
미로 찾기 구현이 필요한 이유는 실제 애플리케이션의 대부분이 격자 구조를 사용하기 때문입니다. 예를 들어, 게임 맵은 타일 격자, 도시 계획은 블록 격자, 이미지 처리는 픽셀 격자로 표현됩니다.
추상적인 그래프보다 격자가 훨씬 직관적이고 시각화하기 쉽습니다. 기존에 재귀적 백트래킹으로 미로를 푼다면 모든 경로를 탐색할 수 있지만 최단 경로를 보장하지 못합니다.
하지만 BFS를 사용하면 첫 번째로 발견한 경로가 자동으로 최단 경로입니다. 미로 찾기 BFS의 핵심 특징은 세 가지입니다.
첫째, 방향 벡터 [(0,1), (1,0), (0,-1), (-1,0)]로 상하좌우 이동을 간결하게 표현합니다. 둘째, 경계 체크와 벽 체크를 조합하여 유효한 이동만 허용합니다.
셋째, 2차원 좌표를 visited set에 직접 저장할 수 있어 추가 변환이 필요 없습니다. 이러한 특징들이 미로 찾기를 효율적이고 이해하기 쉽게 만듭니다.
코드 예제
from collections import deque
def bfs_maze(maze, start, goal):
rows, cols = len(maze), len(maze[0])
visited = set([start])
queue = deque([start])
parent = {start: None}
# 상하좌우 4방향 이동 (우, 하, 좌, 상)
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while queue:
r, c = queue.popleft()
if (r, c) == goal: # 목표 도달
# 경로 역추적
path = []
current = goal
while current:
path.append(current)
current = parent[current]
return path[::-1]
# 4방향 탐색
for dr, dc in directions:
nr, nc = r + dr, c + dc
# 경계 체크, 벽 체크, 방문 체크
if (0 <= nr < rows and 0 <= nc < cols and
maze[nr][nc] == 0 and (nr, nc) not in visited):
visited.add((nr, nc))
parent[(nr, nc)] = (r, c)
queue.append((nr, nc))
return None # 경로 없음
설명
이것이 하는 일: 2차원 미로에서 시작 좌표부터 목표 좌표까지 벽을 피하며 최단 경로를 찾습니다. 격자의 각 칸을 노드로, 상하좌우 연결을 간선으로 간주하여 BFS를 적용합니다.
첫 번째로, directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]은 미로 문제의 핵심 패턴입니다. (0, 1)은 오른쪽, (1, 0)은 아래쪽, (0, -1)은 왼쪽, (-1, 0)은 위쪽 이동을 의미합니다.
대각선 이동을 허용하려면 [(1,1), (1,-1), (-1,1), (-1,-1)]를 추가하면 됩니다. 이 방향 벡터를 사용하면 for 루프로 모든 방향을 간결하게 탐색할 수 있어, 코드 중복을 피하고 실수를 줄일 수 있습니다.
그 다음으로, nr, nc = r + dr, c + dc로 다음 위치를 계산합니다. 현재 위치 (r, c)에 방향 벡터 (dr, dc)를 더하면 이동 후 위치가 나옵니다.
예를 들어, (2, 3)에서 오른쪽으로 이동하면 (2, 3+1) = (2, 4)가 됩니다. 이 방식은 매우 직관적이고 모든 격자 기반 문제에 적용할 수 있는 표준 패턴입니다.
세 번째로, 조건문이 세 가지 검사를 결합합니다. 첫째, 0 <= nr < rows and 0 <= nc < cols로 격자 경계를 벗어나지 않는지 확인합니다.
둘째, maze[nr][nc] == 0으로 벽이 아닌지 확인합니다. 셋째, (nr, nc) not in visited로 이미 방문하지 않았는지 확인합니다.
이 세 조건을 모두 만족해야 유효한 이동입니다. 조건 순서도 중요한데, 경계 체크를 먼저 해야 인덱스 에러를 방지할 수 있습니다.
마지막으로, 경로 역추적은 이전 예제와 동일합니다. parent 딕셔너리에 (부모 좌표)를 저장하고, 목표에서 시작까지 거슬러 올라가며 경로를 복원합니다.
결과는 [(0,0), (0,1), (1,1), (2,1), (2,2)] 같은 좌표 리스트입니다. 이를 시각화하면 미로에서의 실제 이동 경로를 명확하게 볼 수 있습니다.
여러분이 이 코드를 사용하면 게임, 로봇 공학, 경로 계획 등 다양한 분야에서 활용할 수 있습니다. 실무에서는 이를 확장하여 "가중치가 있는 지형", "동적으로 변하는 장애물", "여러 목표 중 가장 가까운 곳 찾기" 같은 복잡한 문제를 해결합니다.
또한 이 패턴은 이미지의 홍수 채우기(flood fill), 섬 개수 세기, 최단 거리 계산 등 수많은 코딩 인터뷰 문제의 기초가 됩니다.
실전 팁
💡 방향 벡터를 상수로 정의하면 코드가 깔끔합니다. DIRECTIONS = [(0,1), (1,0), (0,-1), (-1,0)]를 전역 또는 클래스 상수로 선언하세요.
💡 경계 체크를 먼저 하세요. maze[nr][nc] 전에 경계 체크를 하지 않으면 IndexError가 발생합니다. 조건문의 순서가 중요합니다.
💡 대각선 이동을 허용하려면 방향 벡터에 8개 방향을 모두 추가하세요. 단, 대각선 이동 시 양옆 벽 체크가 필요할 수 있습니다.
💡 visited를 2차원 불린 배열로 구현하면 더 빠를 수 있습니다. visited = [[False] * cols for _ in range(rows)]로 초기화하고 visited[r][c] = True로 표시합니다.
💡 거리만 필요하다면 parent 없이 distance 배열을 사용하세요. distance[nr][nc] = distance[r][c] + 1로 계산하면 경로 역추적 없이 거리만 얻을 수 있습니다.
8. 다중 출발점 BFS
시작하며
여러분이 "여러 지점에서 동시에 불이 번지는 시뮬레이션"이나 "여러 물류 센터 중 가장 가까운 곳 찾기" 같은 문제를 만났다면 어떻게 접근하시겠습니까? 각 출발점마다 BFS를 여러 번 실행하는 것은 비효율적입니다.
이런 문제는 재난 시뮬레이션, 배송 최적화, 영향력 전파 분석 등에서 자주 나타납니다. 출발점이 N개라면 N번의 BFS를 실행하는 것은 O(N × (V+E))의 시간이 걸려 매우 느립니다.
더 나은 방법이 필요합니다. 바로 이럴 때 필요한 것이 다중 출발점 BFS(Multi-Source BFS)입니다.
모든 출발점을 동시에 큐에 넣고 한 번의 BFS를 실행하면, 각 노드에 가장 먼저 도달한 출발점이 자동으로 가장 가까운 출발점이 됩니다.
개요
간단히 말해서, 다중 출발점 BFS는 여러 시작 노드를 모두 큐에 넣고 동시에 탐색을 시작하는 방식입니다. 마치 여러 곳에서 동시에 파도가 퍼져나가듯이, 모든 출발점에서 레벨별로 확장됩니다.
다중 출발점 BFS가 필요한 이유는 효율성과 정확성 때문입니다. 예를 들어, 도시에 5개의 소방서가 있고 화재 발생 시 가장 가까운 소방서를 찾는다면, 5번의 BFS를 실행하는 대신 5개 소방서를 모두 동시에 출발시키면 한 번의 BFS로 모든 위치의 최단 거리를 계산할 수 있습니다.
기존에 각 출발점마다 BFS를 실행하면 O(N × V)의 시간 복잡도입니다. 하지만 다중 출발점 BFS는 O(V+E)로 한 번만 실행하므로 N배 빠릅니다.
출발점이 많을수록 성능 차이가 극적입니다. 다중 출발점 BFS의 핵심 특징은 세 가지입니다.
첫째, 초기 큐에 모든 출발점을 거리 0으로 넣습니다. 둘째, BFS 로직은 단일 출발점과 완전히 동일합니다.
셋째, 각 노드에 처음 도달한 출발점이 자동으로 가장 가까운 출발점입니다. 이러한 특징들이 다중 출발점 문제를 우아하게 해결합니다.
코드 예제
from collections import deque
def multi_source_bfs(graph, sources):
visited = set(sources)
queue = deque()
distances = {}
# 모든 출발점을 큐에 추가 (거리 0)
for source in sources:
queue.append((source, 0))
distances[source] = 0
while queue:
node, dist = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
new_dist = dist + 1
distances[neighbor] = new_dist # 가장 가까운 출발점까지의 거리
queue.append((neighbor, new_dist))
return distances # 각 노드에서 가장 가까운 출발점까지의 거리
# 미로에서 다중 출발점 BFS 예제
def multi_source_maze(maze, sources):
rows, cols = len(maze), len(maze[0])
visited = set(sources)
queue = deque([(s, 0) for s in sources]) # 모든 출발점을 거리 0으로
distances = {s: 0 for s in sources}
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while queue:
(r, c), dist = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if (0 <= nr < rows and 0 <= nc < cols and
maze[nr][nc] == 0 and (nr, nc) not in visited):
visited.add((nr, nc))
distances[(nr, nc)] = dist + 1
queue.append(((nr, nc), dist + 1))
return distances
설명
이것이 하는 일: 여러 출발점에서 동시에 탐색을 시작하여, 각 노드가 가장 가까운 출발점으로부터 얼마나 떨어져 있는지를 한 번에 계산합니다. 마치 여러 돌을 동시에 물에 던졌을 때 물결이 퍼져나가는 것과 같습니다.
첫 번째로, 초기화 단계에서 for source in sources: 루프가 모든 출발점을 큐와 visited에 추가합니다. 이것이 핵심 아이디어입니다.
단일 출발점 BFS에서는 시작 노드 하나만 넣었지만, 여기서는 여러 개를 동시에 넣습니다. 모두 거리 0으로 시작하므로, BFS가 진행되면서 레벨 1, 레벨 2 노드들이 가장 가까운 출발점으로부터 발견됩니다.
그 다음으로, while 루프의 로직은 단일 출발점 BFS와 완전히 동일합니다. 이것이 다중 출발점 BFS의 아름다움입니다.
초기화만 다르게 하면 나머지 코드는 전혀 수정할 필요가 없습니다. 큐에서 노드를 꺼내고, 이웃을 확인하고, 방문하지 않은 노드를 큐에 추가하는 과정이 동일하게 작동합니다.
세 번째로, 각 노드는 처음으로 방문될 때 가장 가까운 출발점에서 도달한 것입니다. 왜일까요?
BFS는 거리 순서대로 탐색하므로, 거리 1인 노드들을 모두 처리한 후 거리 2인 노드들을 처리합니다. 어떤 노드가 출발점 A에서 거리 2, 출발점 B에서 거리 3이라면, 거리 2일 때 먼저 발견되므로 distances에는 2가 기록됩니다.
나중에 거리 3으로 도달하려 해도 이미 visited에 있어 무시됩니다. 마지막으로, 미로 버전에서는 queue = deque([(s, 0) for s in sources])처럼 리스트 컴프리헨션으로 모든 출발점을 한 번에 초기화합니다.
이는 코드를 간결하게 만들어줍니다. 결과 distances는 모든 위치에서 가장 가까운 출발점까지의 거리를 담고 있어, "이 위치에서 가장 가까운 병원은 몇 블록 떨어져 있는가?" 같은 질문에 즉시 답할 수 있습니다.
여러분이 이 코드를 사용하면 복잡한 다중 출발점 문제를 우아하게 해결할 수 있습니다. 실무에서는 "썩은 오렌지(LeetCode 994)", "01 매트릭스(LeetCode 542)", "벽 부수고 이동하기" 같은 고급 문제에 활용됩니다.
또한 재난 확산 시뮬레이션, 영향력 전파 분석, 배송 범위 계산 등 실제 애플리케이션에서도 매우 유용한 패턴입니다.
실전 팁
💡 초기 큐에 모든 출발점을 넣는 것이 핵심입니다. 이후 로직은 일반 BFS와 완전히 동일합니다.
💡 어느 출발점에서 왔는지 알고 싶다면 distances 대신 source_map = {node: 출발점}을 기록하세요. 각 노드가 어느 출발점에 속하는지 알 수 있습니다.
💡 "썩은 오렌지" 문제처럼 시간이 중요하다면 distance 대신 time으로 변수명을 지으세요. 의미가 더 명확해집니다.
💡 출발점이 매우 많다면 set으로 관리하세요. sources = set([...])로 하면 중복 제거와 빠른 조회가 가능합니다.
💡 최대 거리를 구하려면 max(distances.values())를 사용하세요. "모든 곳에 전파되는 데 걸리는 최소 시간"을 계산할 때 유용합니다.
9. BFS와 DFS 비교
시작하며
여러분이 알고리즘 문제를 풀 때 "BFS를 써야 하나, DFS를 써야 하나?"라는 고민을 해본 적 있나요? 둘 다 그래프 탐색 알고리즘인데, 언제 어떤 것을 선택해야 할지 명확하지 않으면 시행착오를 겪게 됩니다.
이런 문제는 코딩 인터뷰, 실무 문제 해결, 알고리즘 대회 등에서 매우 중요합니다. 잘못된 알고리즘을 선택하면 문제를 풀 수 없거나, 성능이 크게 저하되거나, 메모리 초과가 발생할 수 있습니다.
각 알고리즘의 장단점과 사용 사례를 정확히 이해해야 합니다. 바로 이럴 때 필요한 것이 BFS와 DFS의 체계적인 비교입니다.
두 알고리즘의 차이점, 시간/공간 복잡도, 적합한 문제 유형을 명확히 파악하면 올바른 선택을 할 수 있습니다.
개요
간단히 말해서, BFS는 큐를 사용하여 레벨별로 넓게 탐색하고, DFS는 스택(또는 재귀)을 사용하여 깊이 우선으로 탐색합니다. BFS는 최단 경로 찾기에, DFS는 모든 경로 탐색에 적합합니다.
BFS와 DFS를 비교해야 하는 이유는 각각의 강점이 다르기 때문입니다. 예를 들어, "A에서 B까지의 최단 경로"를 찾는다면 BFS가 정답이지만, "미로의 모든 경로 개수"를 찾는다면 DFS가 적합합니다.
문제의 요구사항에 따라 선택이 달라집니다. BFS는 큐를 사용하므로 공간 복잡도가 O(W)인데, 여기서 W는 그래프의 최대 너비입니다.
DFS는 재귀 스택을 사용하므로 O(H)이며, H는 최대 깊이입니다. 넓고 얕은 그래프에서는 DFS가, 좁고 깊은 그래프에서는 BFS가 메모리 효율적입니다.
비교의 핵심 특징은 세 가지입니다. 첫째, BFS는 최단 경로를 보장하지만 DFS는 보장하지 않습니다.
둘째, BFS는 반복문으로, DFS는 재귀로 구현하는 것이 자연스럽습니다. 셋째, BFS는 레벨별 처리에, DFS는 백트래킹에 적합합니다.
이러한 차이를 이해하면 문제에 맞는 알고리즘을 선택할 수 있습니다.
코드 예제
from collections import deque
# BFS: 큐 사용, 레벨별 탐색
def bfs(graph, start):
visited = set([start])
queue = deque([start])
result = []
while queue: # 반복문 사용
node = queue.popleft() # 큐에서 꺼냄 (FIFO)
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
# DFS: 재귀 사용, 깊이 우선 탐색
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
result = [node]
for neighbor in graph[node]: # 재귀 호출
if neighbor not in visited:
result.extend(dfs(graph, neighbor, visited))
return result
# DFS 스택 버전 (BFS와 유사한 구조)
def dfs_iterative(graph, start):
visited = set([start])
stack = [start] # 스택 사용 (리스트)
result = []
while stack:
node = stack.pop() # 스택에서 꺼냄 (LIFO)
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
stack.append(neighbor)
return result
설명
이것이 하는 일: BFS와 DFS는 그래프를 탐색하는 두 가지 근본적으로 다른 접근 방식을 제공합니다. BFS는 가까운 것부터 차례대로, DFS는 한 방향으로 끝까지 파고듭니다.
첫 번째로, 자료구조의 차이가 모든 것을 결정합니다. BFS는 queue.popleft()로 FIFO(선입선출)를 사용하므로, 먼저 넣은 노드가 먼저 처리됩니다.
이것이 레벨별 탐색을 만듭니다. 반면 DFS는 stack.pop()으로 LIFO(후입선출)를 사용하므로, 나중에 넣은 노드가 먼저 처리됩니다.
이것이 깊이 우선 탐색을 만듭니다. 단지 popleft()와 pop()의 차이일 뿐인데, 결과는 완전히 달라집니다.
그 다음으로, BFS는 반복문이 자연스럽고, DFS는 재귀가 자연스럽습니다. 재귀 DFS는 시스템 콜 스택을 자동으로 사용하므로 코드가 매우 간결합니다.
하지만 깊이가 깊으면 스택 오버플로우 위험이 있어, 반복문 버전(dfs_iterative)이 더 안전할 수 있습니다. BFS는 큐를 명시적으로 관리해야 하므로 반복문이 필수입니다.
세 번째로, 탐색 순서가 완전히 다릅니다. 그래프가 A-[B,C], B-[D,E], C-[F]라면, BFS는 [A, B, C, D, E, F] 순서로 방문하지만, DFS는 [A, B, D, E, C, F] 또는 [A, C, F, B, D, E] 순서로 방문합니다(이웃 순서에 따라).
BFS는 거리 1인 노드를 모두 방문한 후 거리 2로 넘어가지만, DFS는 한 경로를 끝까지 탐색한 후 다른 경로로 갑니다. 마지막으로, 사용 사례가 명확하게 구분됩니다.
BFS는 "최단 경로", "최소 이동 횟수", "레벨별 처리"에 사용하고, DFS는 "모든 경로 찾기", "사이클 감지", "위상 정렬", "백트래킹"에 사용합니다. 예를 들어, 미로에서 출구까지의 최단 경로는 BFS, 미로의 모든 가능한 경로는 DFS로 풉니다.
여러분이 이 차이를 이해하면 문제를 보자마자 어떤 알고리즘을 써야 할지 직관적으로 알 수 있습니다. 실무에서는 "최단"이라는 단어가 나오면 BFS, "모든"이라는 단어가 나오면 DFS를 떠올리세요.
또한 두 알고리즘을 결합하는 경우도 있습니다. 예를 들어, BFS로 최단 경로를 찾고, 그 경로에서 DFS로 세부 탐색을 하는 하이브리드 접근도 가능합니다.
실전 팁
💡 "최단", "최소", "레벨"이 나오면 BFS를 생각하세요. "모든", "가능한", "존재하는"이 나오면 DFS를 고려하세요.
💡 재귀 DFS의 깊이 제한은 Python에서 약 1000입니다. sys.setrecursionlimit(10000)으로 늘릴 수 있지만, 반복문 버전이 더 안전합니다.
💡 BFS와 DFS의 시간 복잡도는 모두 O(V+E)로 동일합니다. 공간 복잡도가 다를 뿐입니다.
💡 이진 트리에서 DFS는 전위/중위/후위 순회로 세분화됩니다. 재귀 호출 위치를 바꾸면 됩니다.
💡 양방향 BFS는 BFS의 고급 기법으로, 시작과 목표에서 동시에 탐색하여 만나면 종료합니다. 큰 그래프에서 훨씬 빠릅니다.
10. BFS 시간 복잡도 분석
시작하며
여러분이 대규모 그래프에 BFS를 적용하려는데, "이 알고리즘이 실행 시간이 얼마나 걸릴까?"를 예측해야 한다면 어떻게 하시겠습니까? 단순히 "빠르다"가 아니라 정확한 복잡도 분석이 필요합니다.
이런 문제는 성능 최적화, 알고리즘 선택, 시스템 설계 등에서 필수적입니다. 노드가 100만 개인 그래프에 BFS를 적용할 때 1초가 걸릴지 1시간이 걸릴지 모르면 시스템을 설계할 수 없습니다.
정확한 복잡도 분석이 의사결정의 기초가 됩니다. 바로 이럴 때 필요한 것이 BFS의 시간 복잡도와 공간 복잡도를 정확히 이해하는 것입니다.
O(V+E) 표기법의 의미, 왜 이런 복잡도가 나오는지, 그리고 실제 성능에 어떤 영향을 미치는지를 파악해야 합니다.
개요
간단히 말해서, BFS의 시간 복잡도는 O(V+E)입니다. 여기서 V는 정점(노드) 개수, E는 간선(엣지) 개수입니다.
모든 노드를 한 번씩 방문하고(V), 모든 간선을 한 번씩 확인하기(E) 때문입니다. 시간 복잡도 분석이 필요한 이유는 알고리즘의 확장성을 평가하기 위함입니다.
예를 들어, 페이스북 그래프(수십억 노드)에 BFS를 적용할 수 있을까요? O(V+E)를 알면 대략적인 실행 시간을 예측하고, 필요하면 분산 처리나 최적화를 고려할 수 있습니다.
인접 행렬로 구현하면 모든 간선을 확인하는 데 O(V²)이 걸립니다. 하지만 인접 리스트를 사용하면 실제 존재하는 간선만 확인하므로 O(V+E)로 줄어듭니다.
희소 그래프(E << V²)에서는 엄청난 차이입니다. BFS 복잡도의 핵심 특징은 세 가지입니다.
첫째, 각 노드는 정확히 한 번만 큐에 들어가고 한 번만 처리됩니다(visited 덕분). 둘째, 각 간선은 정확히 한 번만 확인됩니다.
셋째, 공간 복잡도는 O(V)인데, 최악의 경우 모든 노드가 큐에 들어갈 수 있기 때문입니다. 이러한 특징들이 BFS를 효율적인 알고리즘으로 만듭니다.
코드 예제
# BFS 시간 복잡도 분석 예제
from collections import deque
def bfs_complexity_analysis(graph, start):
visited = set([start]) # 공간: O(V)
queue = deque([start]) # 공간: O(V) 최악의 경우
node_count = 0 # 방문한 노드 수
edge_count = 0 # 확인한 간선 수
while queue: # 최대 V번 반복
node = queue.popleft() # O(1)
node_count += 1
# 이 노드의 모든 간선 확인
for neighbor in graph[node]: # 총 E번 실행됨 (모든 노드에 걸쳐)
edge_count += 1
if neighbor not in visited: # O(1) - set 조회
visited.add(neighbor) # O(1) - set 추가
queue.append(neighbor) # O(1) - deque 추가
print(f"방문한 노드: {node_count} (V)")
print(f"확인한 간선: {edge_count} (E)")
print(f"시간 복잡도: O({node_count} + {edge_count}) = O(V + E)")
return visited
# 예제: 완전 그래프와 희소 그래프 비교
def compare_complexity():
# 희소 그래프: E = V (선형 구조)
sparse_graph = {'A': ['B'], 'B': ['C'], 'C': ['D'], 'D': []}
print("희소 그래프 (E ≈ V):")
bfs_complexity_analysis(sparse_graph, 'A')
print()
# 밀집 그래프: E ≈ V² (완전 그래프)
dense_graph = {
'A': ['B', 'C', 'D'],
'B': ['A', 'C', 'D'],
'C': ['A', 'B', 'D'],
'D': ['A', 'B', 'C']
}
print("밀집 그래프 (E ≈ V²):")
bfs_complexity_analysis(dense_graph, 'A')
설명
이것이 하는 일: BFS의 성능을 정확히 분석하여, 주어진 그래프 크기에서 실행 시간과 메모리 사용량을 예측합니다. 이는 알고리즘 선택과 최적화 전략을 수립하는 기초가 됩니다.
첫 번째로, "왜 O(V+E)인가?"를 이해해야 합니다. while 루프는 큐에서 노드를 꺼내는데, visited 덕분에 각 노드는 정확히 한 번만 큐에 들어갑니다.
따라서 while 루프는 최대 V번 실행됩니다. 이것이 O(V) 부분입니다.
각 루프에서 노드의 모든 이웃을 확인하는데, 모든 노드에 걸쳐 총합하면 모든 간선을 한 번씩 확인하게 됩니다. 이것이 O(E) 부분입니다.
따라서 총 시간은 O(V+E)입니다. 그 다음으로, "왜 각 간선이 한 번만 확인되는가?"를 생각해보세요.
무방향 그래프에서 A-B 간선은 A를 방문할 때 한 번, B를 방문할 때 한 번, 총 두 번 확인됩니다. 하지만 이미 방문한 노드는 visited에 있어 큐에 다시 넣지 않으므로, 실제로는 간선당 최대 2번(무방향), 1번(방향) 확인됩니다.
빅오 표기법에서 상수는 무시하므로 여전히 O(E)입니다. 세 번째로, 공간 복잡도를 분석하면 visited는 O(V), queue는 최악의 경우 O(V), parent나 distances 같은 보조 자료구조도 O(V)입니다.
모두 합쳐도 O(V)입니다. 큐의 크기가 정확히 얼마나 될까요?
최악의 경우는 완전 이진 트리의 마지막 레벨에 모든 노드가 동시에 큐에 들어갈 때로, 약 V/2개입니다. 여전히 O(V)입니다.
마지막으로, 실제 성능은 그래프의 형태에 따라 크게 달라집니다. 희소 그래프(E ≈ V, 예: 링크드 리스트)에서는 O(V)에 가깝고, 밀집 그래프(E ≈ V², 예: 완전 그래프)에서는 O(V²)에 가깝습니다.
소셜 네트워크는 보통 E ≈ V*log(V) 정도로 중간입니다. 따라서 실제 성능을 예측하려면 그래프의 특성을 파악해야 합니다.
여러분이 이 분석을 이해하면 "100만 노드, 500만 간선 그래프에 BFS를 적용하면 약 600만 번의 연산"이라고 예측할 수 있습니다. 실무에서는 이를 바탕으로 "이 알고리즘이 1초 안에 끝날까?", "메모리는 충분한가?", "더 빠른 알고리즘이 필요한가?"를 판단합니다.
또한 최적화 포인트를 찾을 수 있습니다. 예를 들어, visited를 set 대신 불린 배열로 바꾸면 상수 배 빨라집니다.
실전 팁
💡 인접 리스트를 사용하세요. 인접 행렬은 O(V²)이 되어 희소 그래프에서 비효율적입니다.
💡 visited를 set으로 구현하면 in 연산이 O(1)입니다. 리스트로 하면 O(V)가 되어 전체가 O(V²)이 됩니다.
💡 실제 성능은 캐시 효율성, 메모리 접근 패턴 등에도 영향을 받습니다. 빅오는 추세를 나타낼 뿐 정확한 시간은 아닙니다.
💡 그래프가 disconnected라면 모든 컴포넌트를 탐색하는 데 여전히 O(V+E)입니다. 각 노드는 여전히 한 번씩만 방문됩니다.
💡 메모리 제약이 있다면 반복적 깊이 제한 DFS(IDDFS)를 고려하세요. BFS의 최단 경로 보장 + DFS의 O(V) 공간을 결합합니다.