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에서는 아직 방문하지 않은 곳이라면 방문 처리 후에 Queue에 넣는다.

DFS와 BFS의 차이

DFS와 BFS는 모두 그래프나 격자를 탐색할 때 사용하는 알고리즘이지만, 탐색하는 순서에 차이가 있다.

구분	DFS	BFS
의미	깊이 우선 탐색	너비 우선 탐색
탐색 방식	한 방향으로 끝까지 탐색	가까운 곳부터 차례대로 탐색
사용 자료구조	Stack 또는 재귀	Queue
특징	가능한 경로를 끝까지 파고듦	같은 거리의 노드를 먼저 탐색
자주 사용되는 문제	모든 경우 탐색, 백트래킹, 연결 요소 탐색	최단거리, 최소 이동 횟수, 확산 문제

• DFS는 한 길을 끝까지 들어간 뒤 더 이상 갈 수 없으면 되돌아오는 방식
• BFS는 시작점에서 가까운 곳을 먼저 모두 확인한 뒤 다음 거리의 노드로 이동하는 방식

따라서 최단거리나 최소 이동 횟수를 구해야 하는 문제에서는 BFS가 자주 사용된다.

왜 BFS가 최단 거리 문제에 적합한데?

• BFS는 시작점에서 가까운 위치부터 차례대로 탐색한다.
• 즉, 거리 1인 위치를 모두 탐색한 뒤 거리 2인 위치를 탐색하고 그 다음 거리 3인 위치를 탐색하는 방식으로 진행된다.
  • 도착 지점에 처음 도달했을 때의 거리가 곧 최단 거리가 된다는 뜻!
  • 단, BFS로 최단 거리를 구할 수 있는 경우는 보통 모든 이동 비용이 동일한 경우이다.

BFS의 대표적인 형태

BFS는 문제 형태에 따라 크게 그래프 BFS와 격자 BFS로 나뉜다.

그래프 BFS

노드와 간선으로 이루어진 구조에서 연결된 노드를 탐색하는 방식

• 위 그래프에서 1번 노드부터 BFS를 수행하면 다음과 같은 순서로 탐색한다.

1 → 2 → 3 → 4 → 5 → 6

• 그래프 BFS에서는 각 노드가 어떤 노드와 연결되어 있는지를 저장하기 위해 보통 인접 리스트를 사용한다.

const graph = [
  [],        // 0번 노드는 사용하지 않는다고 가정
  [2, 3],    // 1번 노드와 연결된 노드
  [1, 4, 5], // 2번 노드와 연결된 노드
  [1, 6],    // 3번 노드와 연결된 노드
  [2],       // 4번 노드와 연결된 노드
  [2],       // 5번 노드와 연결된 노드
  [3]        // 6번 노드와 연결된 노드
];

Javascript 구현

function bfs(start, graph) {
  const visited = Array(graph.length).fill(false);
  const queue = [];
  let head = 0;

  // 시작 노드를 Queue에 넣고 방문 처리
  queue.push(start);
  visited[start] = true;

  while (head < queue.length) {
    // Queue에서 현재 노드 꺼내기
    const current = queue[head++];

    console.log(current);

    // 현재 노드와 연결된 다음 노드 확인
    for (const next of graph[current]) {
      // 아직 방문하지 않은 노드라면
      if (!visited[next]) {
        visited[next] = true;
        queue.push(next);
      }
    }
  }
}

1. visited 배열을 만들어 각 노드의 방문 여부를 저장한다.
2. queue에 시작 노드를 넣는다.
3. 시작 노드를 방문 처리한다.
4. Queue가 빌 때까지 반복한다.
5. Queue에서 현재 노드를 꺼낸다.
6. 현재 노드와 연결된 노드들을 확인한다.
7. 아직 방문하지 않은 노드라면 방문 처리 후 Queue에 넣는다.

즉, 그래프 BFS의 핵심은 현재 노드와 연결된 노드들을 확인하면서, 아직 방문하지 않은 노드를 Queue에 넣는 것이다.

격자 BFS

2차원 배열에서 상하좌우로 이동하며 탐색하는 방식

문제 패턴

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

최단거리 문제

• 시작점에서 도착점까지 가장 짧은 거리를 구하는 문제

최소 이동 횟수 문제

• 특정 위치까지 도달하기 위한 최소 이동 횟수를 구하는 문제

미로 탐색 문제

• 상하좌우로 이동하며 도착점까지 이동하는 문제

영역 탐색 문제

• 격자에서 연결된 영역의 개수나 크기를 구하는 문제

예시 문제 기반 설명

Java

Python

JavaScript

실수 포인트