C# 코딩테스트 강좌, K번째 최단 경로 찾기

문제 설명

주어진 그래프에서 K번째 최단 경로를 찾는 문제입니다. 일반적인 최단 경로 알고리즘(다익스트라 알고리즘, 벨만-포드 알고리즘 등)은 최단 경로를 한 가지만 찾지만, 이 문제에서는 주어진 두 정점 사이의 K번째로 짧은 경로를 찾아야 합니다.

입력 형식:

그래프는 정점과 간선으로 이루어져 있으며, 간선은 각각의 시작 정점, 끝 정점, 그리고 가중치를 가지고 있습니다.
그래프의 정점 수는 N, 간선 수는 M, K는 찾고자 하는 최단 경로의 순위입니다.

출력 형식:

K번째 최단 경로의 길이를 출력합니다. 만약 K번째 최단 경로가 존재하지 않는 경우 -1을 출력합니다.

예제

문제 분석

이 문제를 해결하기 위해 사용되는 알고리즘은 우선순위 큐를 활용한 그래프 탐색입니다. 전통적인 최단 경로 알고리즘을 변형하여 K번째로 짧은 경로를 찾는 접근 방법을 사용합니다. 특히, 다익스트라 알고리즘과 우선순위 큐의 조합으로 필요한 경로를 탐색할 수 있습니다.

문제를 해결하기 위한 과정은 다음과 같습니다:

그래프 데이터를 입력받고, 인접 리스트 형태로 구성합니다.
우선순위 큐를 생성하여 출발 정점에서 시작합니다.
우선순위 큐를 통해 경로를 탐색하고, K번째 최단 경로를 카운트합니다.
K번째 최단 경로가 발견되면 그 길이를 출력합니다.

C# 코드 구현

아래는 위의 과정을 C#으로 구현한 코드입니다.

        
        using System;
        using System.Collections.Generic;

        class Program
        {
            static void Main(string[] args)
            {
                // 입력 받기
                var line = Console.ReadLine().Split();
                int N = int.Parse(line[0]); // 정점 수
                int M = int.Parse(line[1]); // 간선 수
                int K = int.Parse(line[2]); // K번째 최단 경로

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

                // 간선 정보 입력
                for (int i = 0; i < M; i++)
                {
                    line = Console.ReadLine().Split();
                    int a = int.Parse(line[0]);
                    int b = int.Parse(line[1]);
                    int cost = int.Parse(line[2]);
                    graph[a].Add((b, cost));
                }

                // K번째 최단 경로 찾기
                var result = FindKthShortestPath(graph, N, K);
                Console.WriteLine(result);
            }

            static int FindKthShortestPath(List<(int to, int cost)>[] graph, int N, int K)
            {
                var pq = new SortedSet<(int cost, int node, int count)>();
                pq.Add((0, 1, 0)); // (cost, node, count)

                // K번째 최단 경로를 위한 리스트
                var paths = new List[N + 1];
                for (int i = 0; i <= N; i++)
                {
                    paths[i] = new List();
                }

                while (pq.Count > 0)
                {
                    var (cost, node, count) = pq.Min;
                    pq.Remove(pq.Min);

                    paths[node].Add(cost);

                    // K번째 최단 경로를 찾았으면 리턴
                    if (count == K - 1)
                    {
                        return cost;
                    }

                    // 간선 탐색
                    foreach (var edge in graph[node])
                    {
                        pq.Add((cost + edge.cost, edge.to, count + 1));
                    }
                }

                return -1; // K번째 최단 경로가 존재하지 않을 경우
            }
        }

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O((M + N) log N) 입니다. 이유는:

우선순위 큐에 노드가 추가되고 삭제되는 과정에서 log N 시간이 소요됩니다.
모든 간선과 노드를 탐색하므로 그래프의 전체 크기인 O(M + N)만큼의 회차를 수행합니다.

결론

이 강좌에서는 K번째 최단 경로를 찾는 문제를 해결하기 위해 그래프 탐색에 대한 기본 개념을 바탕으로 코드를 구현했습니다. 최단 경로 접근법을 변형해서 K번째 최단 경로를 찾는 방법을 학습하면서, 다양한 알고리즘 문제에서의 전략적 사고를 키울 수 있기를 바랍니다.

다음 강좌에서는 좀 더 복잡한 그래프 탐색 문제를 다루도록 하겠습니다. 추가적으로 궁금한 점이나 피드백이 있다면 댓글로 남겨 주세요!

문제 설명

예제

문제 분석

C# 코드 구현

시간 복잡도 분석

결론

관련