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 자료구조를 사용한다.
• Queue는 먼저 들어온 데이터가 먼저 나가는 구조이다.
  • BFS는 이러한 Queue의 특징을 이용해 가까운 위치부터 순서대로 탐색한다.

BFS의 기본 흐름

BFS의 기본 흐름은 다음과 같다.

1. 시작점을 Queue에 넣는다.
2. 시작점을 방문 처리한다.
3. Queue가 빌 때까지 반복한다.
4. Queue에서 현재 위치를 꺼낸다.
5. 현재 위치와 연결된 다음 위치들을 확인한다.
6. 아직 방문하지 않은 위치라면 방문 처리 후 Queue에 넣는다.

BFS에서 visited가 필요한 이유

• BFS에서는 이미 방문한 위치를 다시 방문하지 않기 위해 visited 배열을 사용한다.
• 방문 처리를 하지 않을 경우, 같은 노드를 반복해서 탐색하는 경우가 생길 수 있다.
  • ex. A ↔ B로 연결되어 있을 때, 방문 처리가 없다면 A 방문 → B 방문 → A 방문 → B 방문 ... 같은 무한 반복이 발생할 수 있다.
• 이를 방지하기 위해 BFS에서는 b아직 방문하지 않은 곳이라면 방문 처리 후에 Queue에 넣는다.

문제 패턴

BFS는 다음과 같은 유형의 문제에서 자주 사용된다. →

예시 문제 기반 설명

Java

Python

JavaScript

실수 포인트