노트

너비 우선 탐색 (BFS)

Breadth-First Search

CS#algorithm · 연결된 개념 5개

쉽게 말하면

BFS는 연못에 돌을 던졌을 때 퍼지는 물결 같아요. 가까운 곳부터 한 겹씩 넓혀 가니까, 어떤 지점에 처음 닿은 순간이 가장 적은 걸음으로 온 길이에요.

비유가 깨지는 곳 먼저 닿은 길이 가장 싼 길이라는 건 간선 비용이 모두 같을 때만 맞아요. 간선마다 비용이 다르면 BFS로는 부족하고 다익스트라를 써야 해요.

시작 정점에서 가까운 정점부터 한 겹씩 넓혀 가며 방문하는 탐색. 큐에 이웃을 넣고 넣은 순서대로 꺼낸다.

function bfs(graph: Record<string, string[]>, start: string) {
  const visited = new Set([start])
  const queue = [start]
  const order: string[] = []
  for (let i = 0; i < queue.length; i++) { // shift 대신 인덱스로 O(1)
    const v = queue[i]
    order.push(v)
    for (const next of graph[v]) {
      if (!visited.has(next)) { visited.add(next); queue.push(next) }
    }
  }
  return order
}
  • 큐에 넣을 때 방문 표시를 해야 같은 정점이 여러 번 들어가지 않는다
  • 시간 O(V + E). 넓은 그래프에서는 한 층 전체가 큐에 담겨 메모리를 많이 쓴다
  • 가중치 없는 그래프의 최단 경로(간선 수가 가장 적은 길)를 보장한다. 처음 도착한 순간이 가장 가까운 경로다
  • 쓰임: 미로 최단 거리, SNS에서 "몇 다리 건너 아는 사람", 웹 크롤러, 트리의 층별 순회

간선마다 비용이 다르면 BFS로는 부족하고 다익스트라 알고리즘를 쓴다. 한 갈래를 깊게 파는 반대 방식은 깊이 우선 탐색 (DFS), 그래프 표현은 그래프.

연결된 개념

이 노트를 가리키는 문서

뜻이 가까운 노트

  • 이진 탐색

    정렬된 배열에서 가운데 값과 찾는 값을 비교해 매번 절반을 버리며 찾는 방법. 원소가 100만 개여도 20번 남짓이면 끝난다(O(log n)). 처음부터 하나씩 확인하는 선형 탐색(Linear Search)은 O(n)이다.

  • 이진 탐색 트리

    각 노드가 자식을 최대 둘 가지고, 왼쪽 서브트리의 모든 값은 노드보다 작고 오른쪽은 크다는 규칙을 지키는 트리. 비교할 때마다 한쪽 가지를 버리므로 정렬된 데이터를 빠르게 찾고 넣을 수 있다.

  • 연결 리스트

    각 노드가 값과 다음 노드를 가리키는 포인터를 가지고 사슬처럼 이어진 자료구조. 리스트는 맨 앞(Head)과 맨 뒤(Tail), 길이 정도만 기억한다. 배열과 달리 인덱스가 없다.

  • 우선순위 큐

    원소마다 우선순위가 있고, 들어온 순서와 상관없이 우선순위가 가장 높은 것부터 꺼내는 추상 자료형(Abstract Data Type, ADT). 같은 우선순위끼리의 순서는 보장하지 않는다. 응급실 대기 순서가 좋은 비유다.

  • 빅오 표기법

    입력 크기 n이 커질 때 알고리즘의 실행 시간(시간 복잡도, Time Complexity)이나 메모리(공간 복잡도, Space Complexity)가 얼마나 빨리 늘어나는지를 대략적으로 나타내는 표기. 정확한 횟수가 아니라 증가하는 모양을 본다. 그래서 상수와 작은 항은 버린다(2n + 5는 O(n)).

보기 옵션