[C#] 알고리즘 - BFS(너비 우선 탐색)

BFS란?

BFS(Breadth-First Search, 너비 우선 탐색)는 그래프나 트리에서 가까운 노드부터 차례대로 탐색하는 알고리즘입니다. 마치 풀이 퍼져나가는 것처럼 동심원 형태로 탐색하기 때문에 최단거리 문제에 매우 유용합니다.

---

BFS를 사용하는 이유

최단거리를 보장하는 이유입니다.

• 거리 1인 모든 지점을 먼저 탐색
• 거리 2인 모든 지점을 그 다음에 탐색
• 거리 3인 모든 지점을 그 다음에 탐색 ...

이런 식으로 진행하기 때문에 처음으로 목표지점에 도달한 순간이 바로 최단거리입니다!

---

BFS vs DFS 비교

구분	BFS	DFS
탐색 방식	너비 우선 (가까운 것부터)	깊이 우선 (끝까지 파고들기)
자료구조	Queue (FIFO)	Stack/재귀 (LIFO)
최단거리	보장	보장 안됨
메모리 사용량	많음	적음
사용 예시	최단거리, 레벨별 탐색	경로 존재 여부, 완전 탐색

---

실전 예제: 게임 맵 최단거리

해당 문제는 프로그래머스에서 검색하여 푸시면 됩니다. 먼저 풀고 나서 보시는걸 추천 드립니다!

1. 핵심 구성 요소

- Queue(큐)

Queue<(int x, int y, int distance)> queue = new Queue<(int, int, int)>();

• Enqueue: 뒤에 추가 (줄 서기)
• Dequeue: 앞에서 제거 (줄에서 빠지기)
• FIFO(First In First Out) 방식으로 동작

- Visited 배열

bool [,] visited = new bool[행, 열];

• 이미 방문한 곳을 다시 방문하지 않도록 체크
• 무한루프 방지의 핵심!

- 방향 배열

int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};

• 상하좌우 4방향 이동을 간단하게 처리

2. 완성된 코드

using System;
using System.Collections.Generic;

class Solution {
    public int solution(int[,] maps) {
        int n = maps.GetLength(0);  // 행의 개수
        int m = maps.GetLength(1);  // 열의 개수
        
        // 방문 체크 배열
        bool[,] visited = new bool[n, m];
        
        // BFS를 위한 큐: (행, 열, 거리)
        Queue<(int, int, int)> queue = new Queue<(int, int, int)>();
        
        // 상하좌우 이동을 위한 방향 배열
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        
        // 시작점 초기화
        queue.Enqueue((0, 0, 1));
        visited[0, 0] = true;
        
        while (queue.Count > 0) {
            var (x, y, dist) = queue.Dequeue();
            
            // 목표지점 도달 체크
            if (x == n-1 && y == m-1) {
                return dist;
            }
            
            // 4방향 탐색
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                // 이동 가능 조건 체크
                if (nx >= 0 && nx < n && ny >= 0 && ny < m
                   && maps[nx, ny] == 1
                   && !visited[nx, ny]) {
                    
                    queue.Enqueue((nx, ny, dist + 1));
                    visited[nx, ny] = true;
                }
            }
        }
        
        return -1;  // 도달 불가능
    }
}

---

BFS 활용 분야

1. 최단거리 문제

• 미로 찾기
• 게임 맵 탐색
• 네트워크 최단 경로

2. 레벨별 탐색

• 트리의 레벨 순회
• 그래프의 깊이별 탐색

3. 연결성 문제

• 섬의 개수 구하기
• 연결 요소 찾기

---

마무리

BFS는 최단거리가 보장되는 강력한 알고리즘입니다. 핵심은:

1. Queue를 이용한 순차적 탐색
2. 동심원 형태로 퍼져나가는 탐색
3. Visited 배열을 통한 중복 방지

이 세가지만 확실히 이해하면 다양한 최단거리 문제를 해결할 수 있습니다!