C# 코딩테스트 강좌, 최단 경로 구하기

이 강좌에서는 C#을 사용하여 알고리즘 시험에서 흔히 출제되는 “최단 경로 구하기” 문제를 풀이해 보겠습니다. 이 주제는 그래프 이론의 기본 개념을 이해하고, 알고리즘 문제 해결 능력을 배양하는 데 매우 유용합니다. 특히, Dijkstra 알고리즘과 같은 인기 있는 알고리즘을 적용하여 이 문제를 어떻게 해결할 수 있는지 살펴보겠습니다.

문제 설명

다음은 “최단 경로 구하기” 문제의 예제입니다:

한 마을에는 N개의 집이 있고, 이 집들은 간선으로 연결되어 있습니다. 각 간선은 이동하는데 소요되는 시간을 나타냅니다. 이제 A 집에서 B 집까지 가는 가장 빠른 경로를 구하세요. 입력으로는 집의 수 N, 간선의 수 M, 각 간선의 정보(시작 집, 끝 집, 소요 시간)가 주어지고, 마지막으로 A 집과 B 집의 번호가 주어집니다.

입력 형식

첫 번째 줄: 집의 수 N (1 ≤ N ≤ 1000)
두 번째 줄: 간선의 수 M (1 ≤ M ≤ 10000)
세 번째 줄부터 M + 2번째 줄까지: 간선 정보 (시작 집, 끝 집, 소요 시간)
마지막 줄: A 집 번호와 B 집 번호

출력 형식

가장 빠른 경로의 소요 시간을 출력합니다. 만약 A 집에서 B 집으로 갈 수 없는 경우 -1을 출력합니다.

해결 방안

이 문제를 해결하기 위해 우리는 그래프 이론의 Dijkstra 알고리즘을 사용합니다. 이 알고리즘은 음의 가중치가 없는 그래프에서 최단 경로를 구하는 데 매우 효과적입니다.

Dijkstra 알고리즘

Dijkstra 알고리즘은 시작 노드에서 다른 모든 노드까지의 최단 경로를 구하는 그리디 알고리즘입니다. 이 알고리즘의 주요 아이디어는 다음과 같습니다:

출발 노드의 최단 거리를 0으로 초기화하고, 다른 모든 노드의 거리는 무한대로 초기화합니다.
우선순위 큐를 사용하여 현재 노드에서 가장 거리가 짧은 노드를 선택합니다.
선택된 노드를 기반으로 인접 노드의 거리 정보를 업데이트합니다.
모든 노드의 최단 거리를 계산할 때까지 이 과정을 반복합니다.

코드 구현

이제 Dijkstra 알고리즘을 C#으로 구현해보겠습니다. 아래는 알고리즘을 사용하여 최단 경로를 구하는 코드입니다:

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        int M = int.Parse(Console.ReadLine());

        // 그래프 초기화
        List>[] graph = new List>[N + 1];
        for (int i = 1; i <= N; i++)
        {
            graph[i] = new List>();
        }

        // 간선 입력 받기
        for (int i = 0; i < M; i++)
        {
            var line = Console.ReadLine().Split();
            int u = int.Parse(line[0]);
            int v = int.Parse(line[1]);
            int w = int.Parse(line[2]);
            graph[u].Add(new Tuple(v, w));
            graph[v].Add(new Tuple(u, w)); // 양방향 간선
        }

        var lastLine = Console.ReadLine().Split();
        int start = int.Parse(lastLine[0]);
        int end = int.Parse(lastLine[1]);

        // 최단 경로 구하기
        var result = Dijkstra(graph, N, start, end);
        Console.WriteLine(result);
    }

    static int Dijkstra(List>[] graph, int N, int start, int end)
    {
        int[] distances = new int[N + 1];
        bool[] visited = new bool[N + 1];
        int INF = int.MaxValue;

        // 거리를 INF로 초기화
        for (int i = 1; i <= N; i++)
        {
            distances[i] = INF;
        }
        distances[start] = 0;

        // 우선순위 큐
        SortedSet> pq = new SortedSet>();
        pq.Add(new Tuple(0, start));

        while (pq.Count > 0)
        {
            var current = pq.Min;
            pq.Remove(current);

            int currDist = current.Item1;
            int currNode = current.Item2;

            if (visited[currNode])
            {
                continue;
            }
            visited[currNode] = true;

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

                if (currDist + weight < distances[nextNode])
                {
                    distances[nextNode] = currDist + weight;
                    pq.Add(new Tuple(distances[nextNode], nextNode));
                }
            }
        }

        return distances[end] == INF ? -1 : distances[end];
    }
}

코드 설명

위의 코드는 최단 경로를 구하는 Dijkstra 알고리즘의 구현입니다:

그래프 초기화: 집의 수 N과 간선의 수 M을 입력받고, 그래프를 리스트로 표현합니다.
간선 입력: 각 간선 정보를 입력받아 그래프에 추가합니다. 이때, 양방향 간선으로 처리합니다.
Dijkstra 함수: 최단 경로를 구하는 로직을 포함합니다. 거리 배열과 방문 배열을 초기화하고, 우선순위 큐를 사용하여 가장 짧은 거리의 노드를 선택합니다.

결론

이번 강좌에서는 C#을 사용하여 최단 경로 문제를 풀어보았습니다. Dijkstra 알고리즘을 통해 그래프에서 최단 경로를 효과적으로 구할 수 있다는 것을 배웠습니다. 이러한 기법은 코딩 테스트 및 실제 개발에서도 매우 유용하게 사용될 수 있습니다. 다양한 문제를 풀어보며 이 알고리즘의 기초를 확실히 다져보시길 바랍니다.