그래프 이론과 깊이 우선 탐색(Depth-First Search) 알고리즘의 원리, C# 예제 코드

 

안녕하세요! 오늘의 기술 면접 지식은 그래프 이론의 한 부분인 깊이 우선 탐색(Depth-First Search, DFS) 알고리즘에 관한 것입니다. 이 포스팅에서는 깊이 우선 탐색 알고리즘의 원리와 C#을 사용한 구현 예시에 대해 알아봅니다.

깊이 우선 탐색 알고리즘 원리

깊이 우선 탐색(DFS)은 그래프를 탐색하는 알고리즘 중 하나로, 한 노드에서 시작하여 최대한 깊게 들어간 후, 더 이상 방문할 수 있는 인접 노드가 없으면 이전 노드로 돌아가는 방식으로 탐색합니다. 이 과정을 모든 노드를 방문할 때까지 반복합니다. DFS는 재귀 호출이나 스택을 사용하여 구현할 수 있습니다.

C#을 사용한 깊이 우선 탐색 구현 예시

using System;
using System.Collections.Generic;

public class Graph
{
    private int _vertices;
    private List<int>[] _adjacencyList;

    public Graph(int vertices)
    {
        _vertices = vertices;
        _adjacencyList = new List<int>[vertices];

        for (int i = 0; i < vertices; i++)
        {
            _adjacencyList[i] = new List<int>();
        }
    }

    public void AddEdge(int source, int destination)
    {
        _adjacencyList[source].Add(destination);
    }

    public void DFS(int startNode)
    {
        bool[] visited = new bool[_vertices];
        DFSUtil(startNode, visited);
    }

    private void DFSUtil(int currentNode, bool[] visited)
    {
        visited[currentNode] = true;
        Console.Write(currentNode + " ");

        foreach (int adjacentNode in _adjacencyList[currentNode])
        {
            if (!visited[adjacentNode])
            {
                DFSUtil(adjacentNode, visited);
            }
        }
    }
}

 

위의 코드는 C#을 사용하여 깊이 우선 탐색 알고리즘을 구현한 예시입니다. 그래프 클래스는 노드와 간선을 관리하며, DFS 메서드를 사용하여 깊이 우선 탐색을 수행합니다.

 

깊이 우선 탐색 알고리즘을 사용하는 예시:

 

Graph graph = new Graph(6);

graph.AddEdge(0, 1);
graph.AddEdge(0, 2);
graph.AddEdge(1, 3);
graph.AddEdge(1, 4);
graph.AddEdge(2, 4);
graph.AddEdge(3, 4);
graph.AddEdge(3, 5);
graph.AddEdge(4, 5);

graph.DFS(0); // 출력: 0 1 3 4 5 2

 

이상으로 깊이 우선 탐색 알고리즘에 대한 기본적인 이해와 C#을 사용한 구현 예시를 살펴봤습니다. 깊이 우선 탐색은 그래프를 탐색하거나 순환 구조를 찾는 데 유용한 알고리즘입니다. 다음 포스팅에서는 또 다른 기술 면접 관련 지식을 다루겠습니다. 기대해주세요!