너비 우선 탐색은 가까운 곳부터 챙기기
크리스가 SNS 기능을 개발하고 있다.
"나와 '1촌'인 친구들, 그리고 '2촌'인 친구들의 친구들... 이렇게 가까운 순서대로 추천 친구 목록을 띄워주고 싶어."
지난번에 배운 DFS(깊이 우선 탐색)를 썼더니 문제가 생겼다.
나와 전혀 모르는 사이인데, 내 친구의 친구의 친구의... 친구를 타고 지구 반대편에 있는 사람을 먼저 추천해 버린 것이다. (DFS는 한 놈만 패니까!)
"아니, 내 주변부터 차근차근 훑어야지!"
이럴 때 필요한 것이 바로 BFS(너비 우선 탐색)다. 호수에 돌을 던지면 물결이 동그랗게 퍼져나가듯, 시작점에서 가까운 노드부터 탐색하는 방식이다.
1. 물결처럼 퍼져나가기
DFS가 "미로 찾기"라면, BFS는 "전염병 확산"이나 "와이파이 신호"와 같다.
이렇게 층(Level) 별로 탐색하기 때문에, BFS를 쓰면 "가장 적은 횟수로 갈 수 있는 최단 거리"를 보장할 수 있다.
2. 구현의 핵심: 큐(Queue)
DFS가 스택(Stack)이나 재귀를 썼다면, BFS는 큐(Queue)를 사용한다.
먼저 발견한 이웃을 줄 세워놓고, 먼저 발견한 순서대로(FIFO) 처리해야 레벨 순서가 꼬이지 않기 때문이다.
자바스크립트 구현 (그래프 순회)
// 그래프 데이터 (인접 리스트)
const graph = {
A: ["B", "C"],
B: ["A", "D", "E"],
C: ["A", "F"],
D: ["B"],
E: ["B", "F"],
F: ["C", "E"]
};
function bfs(startNode) {
const visited = new Set(); // 방문 도장
const queue = [startNode]; // 1. 큐 생성 및 시작점 삽입
visited.add(startNode); // 시작점 방문 처리
// 2. 큐가 빌 때까지 반복
while (queue.length > 0) {
// 3. 맨 앞에서 하나 꺼냄 (Shift)
const currentNode = queue.shift();
console.log("방문:", currentNode);
// 4. 꺼낸 노드의 이웃들을 확인
for (const neighbor of graph[currentNode]) {
// 아직 안 가본 곳이라면?
if (!visited.has(neighbor)) {
visited.add(neighbor); // 도장 찍고
queue.push(neighbor); // 큐에 줄 세우기 (Push)
}
}
}
}
bfs("A");
// 출력 순서: A -> B -> C -> D -> E -> F (거리순 방문)주의: 자바스크립트 배열의 shift()는 맨 앞 요소를 빼고 나머지를 당겨와야 하므로 O(N)의 비용이 든다. 데이터가 매우 많다면, 실제 큐 자료구조(Linked List)를 직접 구현해서 쓰는 것이 좋다. (2장 2강 참고)
3. DFS vs BFS: 언제 무엇을 써야 할까?
이 두 알고리즘은 라이벌 관계다. 상황에 맞춰 골라 써야 한다.
| 특징 | DFS (깊이 우선) | BFS (너비 우선) |
| 자료구조 | 스택 (Stack) / 재귀 | 큐 (Queue) |
| 탐색 방식 | 한 놈만 끝까지 판다. | 주변부터 넓게 훑는다. |
| 장점 | 코드가 단순함(재귀), 메모리를 덜 씀. | 최단 경로를 보장함. |
| 단점 | 해가 없는 경로 깊이 빠질 수 있음. | 큐에 노드를 많이 저장해야 해서 메모리를 많이 씀. |
| 사용처 | 미로 찾기, 사이클 탐지, 백트래킹 | 최단 거리(네비게이션), 친구 추천, 웹 크롤링 |
4. 실전 문제: 최단 거리 구하기
"서울에서 부산까지 거쳐야 하는 최소 도시 개수는?"
이런 문제는 무조건 BFS다. DFS로 풀면 서울 → 강원도 → ... → 부산으로 가는 경로를 찾을 수는 있지만, 그게 제일 빠른 길이라는 보장이 없다. BFS는 가장 먼저 부산에 도착하는 경로가 무조건 최단 경로다.
핵심 정리
이제 길 찾기의 기본은 다 배웠다.
그런데 만약 도시마다 도로 건설 비용이 다르다면? 모든 도시를 연결하되, 건설 비용이 가장 적게 들도록 도로를 깔려면 어떻게 해야 할까?
가성비 최고의 네트워크를 구축하는 방법, 최소 신장 트리(MST)를 알아보자.