9주차

BFS(Breadth-First Search)

개념

그래프나 격자에서 탐색을 할 때, 시작 지점에서 가까운 곳부터 차례대로 탐색하는 알고리즘

• Breadth-First Search의 약자로, 한국어로는 너비 우선 탐색이라고도 부른다.
• 현재 위치에서 갈 수 있는 곳들을 먼저 모두 확인 후에 그 다음 단계로 이동한다고 생각하면 된다.

BFS의 탐색 방식

• BFS는 시작점에서부터 거리가 가까운 순서대로 탐색한다

거리 0: 시작점
거리 1: 시작점과 바로 연결된 지점
거리 2: 거리 1 지점들과 연결된 지점
거리 3: 거리 2 지점들과 연결된 지점

예시

예를 들어 다음과 같은 그래프가 있다면,

      1
    /   \
   2     3
  / \     \
 4   5     6

1번 노드에서 BFS를 수행하면 탐색 순서는 다음과 같다.

1 → 2 → 3 → 4 → 5 → 6

이처럼 BFS는 가까운 노드부터 차례대로 탐색하기 때문에, 최단거리 문제에서 자주 사용된다.

BFS에서 Queue를 사용하는 이유

• BFS는 먼저 발견한 위치를 먼저 탐색해야 하기 때문에, Queue 자료구조를 사용한다.

문제 패턴

예시 문제 기반 설명

Java

Python

JavaScript

실수 포인트