너비 우선 탐색 (BFS)
연못에 돌을 던지면 물결이 고리 모양으로 고르게 퍼집니다. 너비 우선 탐색도 그래프를 같은 방식으로 탐색합니다. 먼저 시작에서 한 걸음 떨어진 곳 전부, 그다음 두 걸음 떨어진 곳 전부, 이런 식입니다. 이 단순한 순서 덕분에 최단 경로를 찾을 수 있습니다.
기본 아이디어
그래프는 간선으로 연결된 노드의 집합입니다. 장소와 도로, 사람과 친구 관계, 미로의 칸과 그 사이의 통로 같은 것입니다. 너비 우선 탐색은 "여기서 출발하면 어디에 갈 수 있고, 최소 몇 걸음이면 되는가?"라는 질문에 답합니다. 아직 방문할 노드를 큐에 담아 둡니다. 맨 앞에서 노드를 꺼내고 새 노드를 맨 뒤에 넣으므로, 노드는 발견된 순서대로 처리됩니다.
단계별 과정
시작 노드를 거리 0으로 큐에 넣습니다. 맨 앞 노드를 꺼냅니다. 아직 보지 않은 이웃마다 거리를 현재 노드보다 1 크게 기록하고, 현재 노드를 도달한 경로로 기억한 뒤, 큐의 맨 뒤에 넣습니다. 이미 본 이웃은 건너뜁니다. 큐가 비거나 목표에 도달할 때까지 반복합니다.
예시
간선 A–B, A–C, B–D, C–D, C–E, D–F가 있는 그래프에서 A부터 시작합니다. 큐에서 A를 꺼내면 거리 1인 B와 C를 찾습니다. B를 꺼내면 거리 2인 D를 찾습니다. C를 꺼내면 D는 이미 봤고, 거리 2인 E를 찾습니다. D를 꺼내면 거리 3인 F를 찾습니다. E와 F에서는 새 노드가 없고 큐가 빕니다. 기억해 둔 노드를 F부터 거꾸로 따라가면 F ← D ← B ← A이므로, A에서 F까지의 최단 경로는 간선 세 개짜리 A → B → D → F입니다.
거리가 정확한 이유
거리 1인 노드는 모두 거리 2인 어떤 노드보다 먼저, 거리 2인 노드는 모두 거리 3인 어떤 노드보다 먼저 큐에 들어갑니다. 노드의 이웃은 그 노드가 큐에서 나올 때만 큐에 들어가기 때문입니다. 그래서 노드에 처음 도달하는 경로는 간선 수가 가장 적고, BFS는 거리를 고칠 필요가 없습니다. 각 노드는 한 번 꺼내지고 각 간선은 양 끝에서 보므로, 작업량은 노드 수와 간선 수의 합에 비례해 늘어납니다.
역사와 활용
Konrad Zuse는 1945년 Plankalkül 언어 연구에서 너비 우선 탐색을 설명했지만, 이 연구는 1972년에야 출판되었습니다. Edward F. Moore는 1959년 미로를 빠져나가는 최단 경로를 찾기 위해 이를 다시 고안했고, C. Y. Lee는 1961년 회로 기판의 배선에 사용했습니다. 오늘날에는 퍼즐의 최소 이동 횟수, 소셜 네트워크의 분리 단계, 웹 크롤러가 먼저 도달하는 페이지, 게임에서 가장 가까운 빈칸을 찾는 데 쓰입니다. 간선에 길이가 있으면 다익스트라 알고리즘이 이를 일반화합니다.
직접 해 보기
앱을 열고 단계를 누르세요. 방문 중인 노드는 강조 표시되고, 큐에서 기다리는 노드는 파란색, 방문한 노드는 초록색이며 각자 거리가 표시됩니다. 큐는 그래프 아래에 맨 앞부터 표시됩니다. 클릭을 목표로 바꾸고 노드를 고르면 그곳에서 멈추고 최단 경로를 볼 수 있습니다. 노드와 간선이 더 많은 새 그래프를 만들어 볼 수도 있습니다.
자주 묻는 질문
BFS의 시간 복잡도는?
노드(정점) V개와 간선 E개에 대해 O(V + E)입니다. 각 노드는 큐에 한 번 들어가고 한 번 나오며, 각 간선은 양 끝에서 검사됩니다. 큐와 거리를 위해 O(V)의 추가 메모리가 필요합니다.
BFS는 왜 큐를 사용하나요?
선입선출이면 노드가 발견된 순서, 즉 거리 순서대로 유지되기 때문입니다. 대신 스택을 쓰면 탐색이 먼저 깊이 파고듭니다. 그것이 깊이 우선 탐색입니다.
BFS로 가중치 그래프의 최단 경로를 찾을 수 있나요?
일반적으로는 아닙니다. 간선의 길이가 아니라 간선 수를 세기 때문입니다. 음수 간선이 없는 가중치 그래프에는 다익스트라 알고리즘을 사용하세요. 모든 가중치가 0 또는 1이면 0-1 BFS라는 변형을 쓸 수 있습니다.
BFS는 어디에 쓰이나요?
퍼즐과 미로를 최소 이동으로 풀기, 소셜 네트워크에서 친구의 친구 찾기, 웹을 단계별로 크롤링하기, 네트워크 브로드캐스트, 그리고 최대 유량 찾기 같은 다른 알고리즘의 구성 요소로 쓰입니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
너비 우선 탐색 해 보기