C# 코딩테스트 강좌, 다익스트라

안녕하세요, 여러분! 오늘은 C#을 사용하여 다익스트라 알고리즘을 구현하고, 이를 통해 알고리즘 문제를 해결하는 방법에 대해 깊이 있게 알아보도록 하겠습니다. 이 강좌에서는 알고리즘의 기본 개념, 문제 정의, C# 코드 구현, 그리고 최적화 방법을 단계별로 설명할 것입니다.

1. 다익스트라 알고리즘이란?

다익스트라 알고리즘은 그래프에서 최단 경로를 찾기 위한 알고리즘입니다. 특히, 모든 간선의 가중치가 0보다 크거나 같을 때 유용하게 사용됩니다. 이 알고리즘은 특정 노드에서 시작하여 다른 모든 노드까지의 최단 경로를 효율적으로 계산합니다.

다익스트라 알고리즘의 기본 원리는 다음과 같습니다:

시작 노드에서 거리 값을 초기화합니다. 시작 노드의 거리는 0, 다른 노드는 무한대로 설정합니다.
현재 노드에서 인접한 노드로 이동할 때, 현재 노드를 통해 인접 노드에 도달하는 거리가 더 짧은 경우 거리 값을 업데이트합니다.
모든 노드가 방문될 때까지 이 과정을 반복합니다.
최종적으로 각 노드까지의 최단 거리를 출력합니다.

2. 문제 정의

이번에 함께 풀어볼 문제는 “최단 경로 찾기”입니다. 주어진 그래프의 노드와 간선이 있고, 특정 출발 노드에서 다른 모든 노드까지의 최단 거리를 구하는 것입니다.

문제의 입력은 다음과 같습니다:

첫 번째 줄: 노드의 수 N (1 <= N <= 100,000)과 간선의 수 M (1 <= M <= 200,000)
두 번째 줄부터 M개의 줄: 각 간선의 정보 (A, B, C)로, 여기서 A와 B는 노드 번호, C는 두 노드 사이의 거리입니다.
마지막 줄: 출발 노드 K

출력은 각 노드까지의 최단 거리입니다. 도달할 수 없는 노드는 “INF”로 표시합니다.

3. 알고리즘 설계

다익스트라 알고리즘을 C#으로 구현하기 위해 필요한 라이브러리와 데이터 구조로는 다음을 사용할 수 있습니다:

우선순위 큐: 거리 정보를 관리하기 위해 사용합니다.
그래프 표현: 인접 리스트 또는 인접 행렬을 통해 그래프를 표현합니다.
거리 배열: 각 노드에 대한 최단 거리 값을 저장합니다.

4. C# 코드 구현

먼저 C#에서 다익스트라 알고리즘을 구현하기 위한 전체 코드를 살펴보겠습니다.


using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        int N = input[0];
        int M = input[1];

        List>[] graph = new List>[N + 1];
        for (int i = 0; i <= N; i++)
            graph[i] = new List>();

        for (int i = 0; i < M; i++)
        {
            input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            graph[input[0]].Add(new Tuple(input[1], input[2]));
            graph[input[1]].Add(new Tuple(input[0], input[2])); // 무향 그래프인 경우
        }

        int K = int.Parse(Console.ReadLine());
        int[] distances = Dijkstra(graph, N, K);

        for (int i = 1; i <= N; i++)
        {
            Console.WriteLine(distances[i] == int.MaxValue ? "INF" : distances[i].ToString());
        }
    }

    static int[] Dijkstra(List>[] graph, int N, int start)
    {
        int[] distances = new int[N + 1];
        for (int i = 1; i <= N; i++)
            distances[i] = int.MaxValue;
        distances[start] = 0;

        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.Enqueue(start, 0);

        while (priorityQueue.Count > 0)
        {
            var current = priorityQueue.Dequeue();
            int currentNode = current.Item1;
            int currentDistance = current.Item2;

            if (currentDistance > distances[currentNode]) continue;

            foreach (var edge in graph[currentNode])
            {
                int nextNode = edge.Item1;
                int weight = edge.Item2;

                if (distances[currentNode] + weight < distances[nextNode])
                {
                    distances[nextNode] = distances[currentNode] + weight;
                    priorityQueue.Enqueue(nextNode, distances[nextNode]);
                }
            }
        }

        return distances;
    }
}

5. 코드 설명

위의 코드에서는 다익스트라 알고리즘을 구현하였습니다. 각 부분의 기능을 자세히 설명하겠습니다.

5.1. 메인 함수

메인 함수에서는 입력을 받고, 그래프를 구성한 후 다익스트라 함수를 호출합니다.

입력을 받아 N과 M을 구분합니다.
각 노드에서 리스트로 표현된 그래프를 초기화합니다.
주어진 간선 정보를 기반으로 그래프를 구성합니다.
출발 노드 K를 입력받고, 다익스트라 함수를 호출하여 최단 거리 배열을 반환받습니다.
각 노드의 최단 거리를 출력합니다. 도달할 수 없는 경우 “INF”를 표시합니다.

5.2. Dijkstra 함수

Dijkstra 함수는 다익스트라 알고리즘의 핵심 로직을 포함하고 있습니다.

거리 배열을 초기화합니다.
우선순위 큐를 사용하여 현재 노드 정보를 저장하고, 가장 작은 거리를 가진 노드를 선택합니다.
현재 노드와 인접한 노드들에 대해 최단 거리 업데이트를 수행합니다.

6. 테스트 케이스

이제 다익스트라 알고리즘이 잘 작동하는지 테스트하기 위해 몇 가지 테스트 케이스를 만들어 보겠습니다.

6.1. 테스트 케이스 1

입력:

출력:

6.2. 테스트 케이스 2

입력:

출력:

7. 정리 및 최적화

이번 강좌에서는 C#을 사용하여 다익스트라 알고리즘을 구현하고, 최단 경로 찾기 문제를 해결했습니다. 다익스트라 알고리즘의 효율성을 높이기 위해 다음과 같은 최적화 방법을 고려할 수 있습니다:

우선순위 큐 대신 Fibonacci 힙을 사용하면, 최악의 경우 O(V log V) 시간 복잡도로 계산할 수 있습니다.
그래프가 희소한 경우 인접 리스트를 사용하여 메모리를 절약할 수 있습니다.

다음 강좌에서 다루게 될 주제는 “벨만-포드 알고리즘”으로, 이 알고리즘은 음수 가중치 간선이 존재할 때 최단 경로를 찾는 데 유용합니다. 여러분의 알고리즘 실력 향상에 도움이 되었으면 좋겠습니다! 감사합니다.