너비 우선 탐색 ( BFS )

너비 우선 탐색 ( BFS , Breadth - First Search )

자료구조 내에서 찾고자 하는 데이터를 찾는 방식은 여러 알고리즘과 기법이 존재한다.

너비 우선 탐색은 그래프 탐색 알고리즘 중 하나이다. 가까운 정점부터 탐색을 진행하는 방식이다.

시작 정점으로부터 거리가 가까운 정점들을 먼저 방문하고 그 다음 거리에 있는 정점들을 방문하는 방식으로 탐색이 진행된다. 

이런 방식은 경로의 길이를 기준으로 탐색하는 문제, 최단 경로를 찾는 문제에서 특히 효과적이다.

 

시작 정점에서 출발해 연결된 정점들을 순서대로 Queue에 넣고
큐에서 꺼낸 정점을 기준으로 다시 그 정점에 연결된 이웃들을 큐에 넣으며 탐색을 확장한다.

깊이 우선 탐색이 한 경로를 깊에 따라가는 방식이라면,

너비 우선 탐색은 한 계층씩 넓게 탐색해 나간다.

 

 

BFS 는 다음 상황에서 매우 강력하다

1. 최단 거리 찾기

가중치가 없는 그래프라면 , BFS 가 공식적으로 최단 경로를 찾는 알고리즘이다

• 미로에서 가장 빠르게 출구 찾기
• 캐릭터 이동 거리 계산
• 최소 이동 횟수 문제

 

2. 수평 레벨 단위 탐색

• 계층 구조 ( Level order traversal )
• AI 범위 탐색
• 타일맵 / 필드에서 거리 탐색

 

3. 모든 노드를 효율적으로 방문해야 할 때

 

 

 

작동 원리

BFS 는 다음과 같은 흐름으로 동작한다.

BFS 는 큐 ( Queue )를 사용한다.

1. 시작 노드를 큐에 넣는다
2. 큐에서 하나 꺼낸 뒤 방문 처리
3. 인접한 노드 중 방문 안 한 것들을 큐에 추가한다
4. 큐가 빌 때까지 반복한다

큐에 넣고 → 차례대로 꺼내면서 → 주변을 확장

큐는 선입선출 ( FIFO ) 방식이기 때문에 방문 순서가 거리 순서와 동일해진다.

 

 

 

의사코드 ( Pseudocode )

BFS(graph, start)
    visited 배열 초기화
    큐에 start 정점을 넣고 방문 처리

    while (큐가 비어 있지 않음)
        현재 정점 = 큐에서 꺼냄

        for (현재 정점과 연결된 인접 정점 next에 대해 반복)
            if (next가 아직 방문되지 않았다면)
                방문 처리
                큐에 추가

• 큐를 이용해 탐색 범위를 넓혀가며 방문한다
• 먼저 방문된 정점일수록 먼저 탐색되기 때문에 최단 거리 탐색 결과로도 활용 가능하다

 

 

예시 코드 ( 그래프 기반 )

using System;
using System.Collections.Generic;

class BFSExample
{
    static List<int>[] graph;
    static bool[] visited;

    static void Main()
    {
        int n = 5;
        graph = new List<int>[n];
        visited = new bool[n];

        for (int i = 0; i < n; i++)
            graph[i] = new List<int>();

        AddEdge(0, 1);
        AddEdge(0, 2);
        AddEdge(1, 3);
        AddEdge(2, 4);

        BFS(0);
    }

    static void AddEdge(int a, int b)
    {
        graph[a].Add(b);
        graph[b].Add(a);
    }

    static void BFS(int start)
    {
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(start);
        visited[start] = true;

        while (queue.Count > 0)
        {
            int node = queue.Dequeue();
            Console.WriteLine($"Visit: {node}");

            foreach (var next in graph[node])
            {
                if (!visited[next])
                {
                    visited[next] = true;
                    queue.Enqueue(next);
                }
            }
        }
    }
}

 

 

 

시간 복잡도

• 정점 수 : V
• 간선 수 : E

자료구조	시간 복잡도	설명
인접 리스트	O( V + E )	정점 ( V )과 간선 ( E )을 한 번씩 확인한다
인접 행렬	O( V² )	모든 정점 쌍 확인이 필요하다
공간 복잡도	O( V )	방문 체크 배열과 큐를 사용한다

• BFS 는 각 정점과 간선을 한 번씩만 확인하기 때문에 인접 리스트 방식에서는 효율적이다.

 

 

정리

• 가까운 곳부터 차례대로 방문하는 너비 우선 탐색
• 최단 거리 문제에서 필수이다