C# 코딩테스트 강좌, 너비 우선 탐색

안녕하세요, 여러분! 오늘은 C#를 이용한 코딩테스트에서 중요하게 다뤄지는 알고리즘 중 하나인 너비 우선 탐색(BFS, Breadth-First Search)에 대해서 깊이 있게 알아보도록 하겠습니다. BFS는 그래프 또는 트리 데이터 구조를 탐색하는 알고리즘으로, 최단 경로 문제를 해결하거나, 특정 노드를 찾는 데 유용하게 쓰입니다.

1. 너비 우선 탐색(BFS)란?

BFS는 Queue(큐) 자료 구조를 사용하여 구현되는 탐색 알고리즘입니다. 이 알고리즘은 주어진 노드에서 시작하여 그 노드에 인접한 노드들을 탐색한 다음, 탐색한 노드의 인접 노드들을 다시 탐색하는 방식으로 진행됩니다. 이 방식은 점점 더 넓은 영역을 탐색하게 되어 ‘너비 우선’이라는 이름이 붙여졌습니다.

2. BFS의 특징

  • 최단 경로 탐색: BFS는 모든 간선의 가중치가 동일할 때, 최단 경로를 찾기에 적합합니다.
  • 햇빛 탐사: BFS는 가까운 노드를 먼저 방문하기 때문에, ‘햇빛’이 비추는 방식으로 탐색합니다.
  • 큐를 사용: 탐색 순서를 저장하기 위해 큐를 사용하여, 방문해야 할 노드를 FIFO(선입 선출) 방식으로 관리합니다.

3. BFS의 작동 원리

BFS의 기본적인 작동 방식은 다음과 같습니다:

  1. 탐색을 시작할 노드를 큐에 추가하고 방문 표기를 합니다.
  2. 큐에서 노드를 제거하고, 이 노드의 인접한 모든 노드를 체크합니다.
  3. 인접한 노드가 아직 방문하지 않았다면, 큐에 추가하고 방문 표기를 합니다.
  4. 큐가 비어있지 않을 때까지 2번과 3번 과정을 반복합니다.

4. 문제 풀이

이번에는 실제 코딩 테스트에서 나올 법한 문제를 통해 BFS를 이해해보겠습니다.

문제: ‘단지 번호 붙이기’

우리는 n × n 크기의 0과 1로 이루어진 배열을 가지고 있습니다. 여기서 1은 집이 존재하는 곳을 의미하고, 0은 집이 없는 곳을 의미합니다. 연결된 집을 하나의 단지로 보고, 단지의 번호를 붙이기 위해 BFS를 사용합니다. 같은 단지에 속한 집의 개수를 세어 각 단지의 크기를 출력하는 문제입니다.

입력

5
01101
11011
11100
00011
00000

출력

3
2
1

5. C# 코드 구현

이 문제를 BFS를 이용하여 해결하기 위한 C# 코드를 아래와 같이 작성해보았습니다.


using System;
using System.Collections.Generic;

class Program
{
    static int n;
    static int[,] map;
    static bool[,] visited;
    static int[] dx = { 1, -1, 0, 0 };
    static int[] dy = { 0, 0, 1, -1 };

    static void Main()
    {
        n = int.Parse(Console.ReadLine());
        map = new int[n, n];
        visited = new bool[n, n];

        for (int i = 0; i < n; i++)
        {
            string line = Console.ReadLine();
            for (int j = 0; j < n; j++)
            {
                map[i, j] = line[j] - '0';
            }
        }

        List results = new List();

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (map[i, j] == 1 && !visited[i, j])
                {
                    results.Add(BFS(i, j));
                }
            }
        }

        results.Sort();
        Console.WriteLine(results.Count);
        foreach (int count in results)
        {
            Console.WriteLine(count);
        }
    }

    static int BFS(int startX, int startY)
    {
        Queue<(int, int)> queue = new Queue<(int, int)>();
        queue.Enqueue((startX, startY));
        visited[startX, startY] = true;

        int count = 0;

        while (queue.Count > 0)
        {
            var (x, y) = queue.Dequeue();
            count++;

            for (int i = 0; i < 4; i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 0 && ny >= 0 && nx < n && ny < n && map[nx, ny] == 1 && !visited[nx, ny])
                {
                    queue.Enqueue((nx, ny));
                    visited[nx, ny] = true;
                }
            }
        }

        return count;
    }
}

6. 코드 설명

위의 C# 코드는 다음과 같은 방식으로 작동합니다:

  1. 입력으로 n을 받아 n × n 크기의 집 배치 정보를 2D 배열에 저장합니다.
  2. visited 배열을 통해 각 집의 방문 여부를 기록합니다.
  3. 중첩된 for 루프를 사용하여 모든 집을 탐색하되, 방문하지 않은 집에 대해서만 BFS를 실행합니다.
  4. BFS 메소드는 큐를 사용하여 시작점에서 연결된 집을 탐색하고, 연결된 집의 수를 셉니다.
  5. 모든 단지의 크기를 리스트에 저장하고, 정렬하여 출력합니다.

7. 결론

이번 강좌에서는 너비 우선 탐색(BFS)을 활용한 문제를 통해 코딩 테스트에서 어떻게 문제를 해결할 수 있는지 살펴보았습니다. BFS는 다양한 문제에 적용할 수 있는 강력한 도구입니다. 그래프를 탐색할 때, 최단 경로를 찾을 때 등의 상황에서 BFS의 이해는 아주 중요합니다.

계속해서 BFS에 대한 예제와 더 복잡한 문제를 풀어보며 실력을 쌓아 보세요. 질문이나 의견이 있으시면 언제든 댓글로 남겨주세요. 다음 시간에는 또 다른 알고리즘에 대해 다루도록 하겠습니다!

© 2023 코딩테스트 강좌. All rights reserved.