[Algorithm] BFS (너비 우선 탐색) 알고리즘

BFS(Breadth-First Search) 그래프나 트리와 같은 자료구조를 탐색하는 알고리즘이다. 시작 노드에서 가까운 노드들을 먼저 모두 탐색하는 방식이며, DFS와 달리 최단 경로를 찾는 데 효과적이다.

---

알고리즘의 원리

BFS는 Queue(큐) 자료구조를 사용하여 구현한다.
Queue는 먼저 들어온 데이터가 먼저 나가는 특성을 가지고 있어, 시작 노드로부터의 거리가 동일한 노드들을 순서대로 탐색하는 데 적합하다.

1. 시작 노드를 Queue에 넣고 방문 처리한다.
2. Queue가 빌 때까지 다음 과정을 반복한다.
3. Queue에서 노드를 하나 꺼낸다.
4. 꺼낸 노드와 연결된 이웃 노드들 중 아직 방문하지 않은 노드를 모두 Queue에 넣고 방문 처리한다.

이 과정을 거치면 시작 노드로부터 한 단계씩 확장하며 모든 노드를 탐색하게 된다.

C# 코드 구현

BFS는 Queue를 이용한 반복문으로 구현하는 것이 가장 일반적이다.
아래 코드는 프로그래머스 사이트의 네트워크 문제를 해결하기 위한 BFS 구현 예시다.

using System;
using System.Collections.Generic;

public class Solution
{
    public int solution(int n, int[,] computers)
    {
        bool[] visited = new bool[n];
        int networkCount = 0;

        // 모든 컴퓨터를 순회하며 네트워크를 찾는다.
        for (int i = 0; i < n; i++)
        {
            // 아직 방문하지 않은 컴퓨터를 발견하면 새로운 네트워크로 간주
            if (!visited[i])
            {
                networkCount++;
                BFS(i, n, computers, visited);
            }
        }

        return networkCount;
    }

    // BFS 탐색을 수행하여 하나의 네트워크를 모두 방문 처리하는 함수
    private void BFS(int startNode, int n, int[,] computers, bool[] visited)
    {
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(startNode);
        visited[startNode] = true;

        while (queue.Count > 0)
        {
            int currentNode = queue.Dequeue();

            // 현재 컴퓨터와 연결된 모든 컴퓨터를 확인
            for (int i = 0; i < n; i++)
            {
                // 자기 자신이 아니고, 연결되어 있고, 아직 방문하지 않았다면
                if (currentNode != i && computers[currentNode, i] == 1 && !visited[i])
                {
                    visited[i] = true;
                    queue.Enqueue(i);
                }
            }
        }
    }
}