C# 코딩테스트 강좌, 깊이 우선 탐색

안녕하세요, 여러분! 오늘은 C#을 이용한 코딩테스트 준비를 위한 깊이 우선 탐색(DFS) 알고리즘에 대해 깊이 있게 알아보도록 하겠습니다. 깊이 우선 탐색은 트리나 그래프 구조를 탐색하기 위해 사용되는 효율적인 알고리즘입니다. 이 글에서는 DFS의 기본 개념, 구현 방법, 실제 문제를 통해 이를 어떻게 활용할 수 있는지에 대해 단계별로 설명하겠습니다.

1. 깊이 우선 탐색(DFS)란?

깊이 우선 탐색(DFS, Depth-First Search)은 그래프의 모든 노드를 방문하는 탐색 기법입니다. 이 알고리즘은 한 노드에서 가능한 깊게 탐색한 후, 더 이상 나아갈 수 없을 때 가장 마지막에 방문했던 노드로 돌아가 다른 경로를 탐색하는 방식입니다.

1.1 기본 원리

DFS는 스택을 사용해 구현할 수 있으며, 재귀 함수를 이용해 간편하게 처리할 수 있습니다. DFS의 기본적인 원리는 다음과 같습니다:

시작 노드를 선택합니다.
방문한 노드를 기록합니다.
인접한 노드 중 방문하지 않은 노드를 선택하여 재귀적으로 DFS를 호출합니다.
더 방문할 노드가 없으면 이전 노드로 돌아갑니다.

2. DFS의 시간 복잡도

DFS의 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점(노드)의 수, E는 간선의 수를 의미합니다. 이는 그래프의 모든 노드를 한 번씩 방문하고, 모든 간선도 한 번씩 확인하기 때문입니다. 공간 복잡도는 사용되는 스택에 따라 다르며, 최악의 경우 O(V)입니다.

3. DFS 구현하기

이제 C#으로 DFS를 구현해 보겠습니다. 아래의 코드는 그래프를 인접 리스트 형식으로 표현하고 DFS를 구현한 예제입니다.


using System;
using System.Collections.Generic;

class Graph
{
    private int V; // 정점의 수
    private List[] adj; // 인접 리스트

    public Graph(int v)
    {
        V = v;
        adj = new List[V];
        for (int i = 0; i < V; i++)
        {
            adj[i] = new List();
        }
    }

    public void AddEdge(int v, int w)
    {
        adj[v].Add(w); // 노드 v에 노드 w를 추가
    }

    public void DFS(int v)
    {
        bool[] visited = new bool[V]; // 방문 여부 배열
        DFSUtil(v, visited); // 재귀 호출
    }

    private void DFSUtil(int v, bool[] visited)
    {
        visited[v] = true; // 현재 노드 방문
        Console.Write(v + " "); // 현재 노드 출력

        foreach (int neighbor in adj[v])
        {
            if (!visited[neighbor]) // 인접한 노드가 방문되지 않았으면
            {
                DFSUtil(neighbor, visited); // 재귀 호출
            }
        }
    }
}

class Program
{
    static void Main(string[] args)
    {
        Graph g = new Graph(4);
        g.AddEdge(0, 1);
        g.AddEdge(0, 2);
        g.AddEdge(1, 2);
        g.AddEdge(2, 0);
        g.AddEdge(2, 3);
        g.AddEdge(3, 3);

        Console.WriteLine("Depth First Traversal (시작 노드 2):");
        g.DFS(2);
    }
}

3.1 코드 설명

위의 코드는 다음과 같은 구조로 되어 있습니다:

Graph 클래스: 그래프의 정점 수와 인접 리스트를 포함합니다.
AddEdge 메서드: 두 노드 사이의 간선을 추가합니다.
DFS 메서드: DFS 탐색을 수행하기 위해 방문 여부 배열을 초기화하고, DFSUtil를 호출합니다.
DFSUtil 메서드: 재귀적으로 DFS를 수행하며, 방문한 노드를 출력합니다.

4. 알고리즘 문제: 섬의 개수 세기

이제 DFS를 활용하여 실제 문제를 해결해 보겠습니다. 문제는 ‘섬의 개수 세기’입니다.

4.1 문제 설명

주어진 2차원 배열은 바다(0)와 육지(1)로 구성되어 있습니다. 섬은 육지(1)의 집합으로, 서로 연결된 육지들로 구성됩니다. 섬이란 수직 또는 수평으로 서로 인접해 있는 육지의 집합입니다. 이 2차원 배열에서 섬의 개수를 세는 프로그램을 작성하시오.

4.2 접근 방법

이 문제를 해결하기 위해 다음과 같은 단계를 수행하겠습니다:

2차원 배열을 순회하며, 육지(1)를 발견하면 DFS를 호출합니다.
DFS 내에서 연결된 모든 육지를 방문하며 카운트를 증가시킵니다.
모든 육지를 다 탐색한 후 섬의 개수를 반환합니다.

4.3 C# 코드 구현


using System;

class IslandCounter
{
    private int[,] grid;
    private int rows, cols;

    public IslandCounter(int[,] grid)
    {
        this.grid = grid;
        rows = grid.GetLength(0);
        cols = grid.GetLength(1);
    }

    public int CountIslands()
    {
        bool[,] visited = new bool[rows, cols];
        int count = 0;

        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                if (grid[i, j] == 1 && !visited[i, j])
                {
                    DFS(i, j, visited); // DFS 호출
                    count++;
                }
            }
        }
        return count;
    }

    private void DFS(int i, int j, bool[,] visited)
    {
        if (i >= rows || i < 0 || j >= cols || j < 0 || grid[i, j] == 0 || visited[i, j])
            return;

        visited[i, j] = true; // 방문 처리

        // 인접한 8개 방향으로 DFS 호출
        DFS(i + 1, j, visited);
        DFS(i - 1, j, visited);
        DFS(i, j + 1, visited);
        DFS(i, j - 1, visited);
        DFS(i + 1, j + 1, visited);
        DFS(i - 1, j - 1, visited);
        DFS(i + 1, j - 1, visited);
        DFS(i - 1, j + 1, visited);
    }
}

class Program
{
    static void Main(string[] args)
    {
        int[,] grid = new int[,]
        {
            { 1, 1, 0, 0, 0 },
            { 0, 1, 0, 0, 1 },
            { 0, 0, 0, 1, 1 },
            { 0, 0, 0, 0, 0 },
            { 1, 0, 1, 0, 1 }
        };

        IslandCounter counter = new IslandCounter(grid);
        Console.WriteLine("섬의 개수: " + counter.CountIslands());
    }
}

4.4 코드 설명