C# 코딩테스트 강좌, 가장 빠른 버스 노선 구하기

현대 사회에서 대중교통은 중요한 역할을 하고 있으며, 특히 버스를 이용하는 경우 많은 사람들이 최적의 노선을 찾는 데 어려움을 겪곤 합니다. 이번 강좌에서는 가장 빠른 버스 노선 구하기 문제를 해결하는 과정을 살펴보겠습니다. 이 문제를 해결하기 위해 C#을 사용하여 알고리즘과 데이터 구조를 활용할 것입니다.

문제 정의

주어진 여러 개의 버스 노선과 각 노선의 소요 시간을 바탕으로 시작 지점에서 목적지까지 이동하는 가장 빠른 경로를 구하는 문제입니다.
다음과 같은 입력값을 가집니다:

  • 정점 (Vertex): 버스 정류장
  • 간선 (Edge): 버스 노선
  • 가중치 (Weight): 소요 시간

입력 예시

        5 6
        1 2 3
        1 3 2
        2 3 1
        1 4 1
        2 4 5
        3 5 1

여기서 첫 줄은 정점과 간선의 개수를 나타내며, 다음 각 줄은 정류장 간의 관계와 소요 시간을 보여줍니다.

문제 해결 과정

1단계: 그래프 모델링

위 문제를 해결하기 위해, 버스 정류장을 정점으로 하고, 버스 노선과 소요 시간을 간선으로 하는 그래프를 구성해야 합니다.
이를 위해, 각 정류장과 그 간선의 정보를 담은 인접 리스트를 생성합니다.

2단계: 최단 경로 알고리즘 선택

최단 경로를 찾기 위해 여러 알고리즘이 있지만, 가중치가 있는 간선이 있을 때는 Dijkstra 알고리즘을 사용하는 것이 적합합니다.
Dijkstra 알고리즘은 각 정점까지의 최단 거리를 효과적으로 계산할 수 있는 방법입니다.

3단계: C# 코드 구현

자, 이제 위 내용을 바탕으로 C# 코드를 작성해 보겠습니다. 아래 코드는 Dijkstra 알고리즘을 구현하여 주어진 그래프에서 최단 경로를 찾는 방법을 보여줍니다. 

        using System;
        using System.Collections.Generic;

        class Program
        {
            static void Main(string[] args)
            {
                int vertexCount = 5; // 정점의 수
                int[,] graph = new int[vertexCount + 1, vertexCount + 1];
                for (int i = 1; i <= vertexCount; i++)
                    for (int j = 1; j <= vertexCount; j++)
                        graph[i, j] = (i == j) ? 0 : int.MaxValue;

                // 간선 추가 (소요 시간)
                graph[1, 2] = 3;
                graph[1, 3] = 2;
                graph[2, 3] = 1;
                graph[1, 4] = 1;
                graph[2, 4] = 5;
                graph[3, 5] = 1;

                // Dijkstra 알고리즘 호출
                int[] shortestPath = Dijkstra(graph, vertexCount, 1);

                // 결과 출력
                Console.WriteLine("정점 1에서 다른 정점까지의 최단 거리:");
                for (int i = 1; i <= vertexCount; i++)
                {
                    Console.WriteLine($"정점 1 -> 정점 {i}: {(shortestPath[i] == int.MaxValue ? "도달할 수 없음" : shortestPath[i].ToString())}");
                }
            }

            static int[] Dijkstra(int[,] graph, int vertexCount, int start)
            {
                bool[] visited = new bool[vertexCount + 1];
                int[] distance = new int[vertexCount + 1];

                for (int i = 1; i <= vertexCount; i++)
                {
                    distance[i] = (i == start) ? 0 : int.MaxValue;
                }

                for (int count = 0; count < vertexCount - 1; count++)
                {
                    int u = MinDistance(distance, visited, vertexCount);
                    visited[u] = true;

                    for (int v = 1; v <= vertexCount; v++)
                    {
                        if (!visited[v] && graph[u, v] != int.MaxValue &&
                            distance[u] != int.MaxValue &&
                            distance[u] + graph[u, v] < distance[v])
                        {
                            distance[v] = distance[u] + graph[u, v];
                        }
                    }
                }

                return distance;
            }

            static int MinDistance(int[] distance, bool[] visited, int vertexCount)
            {
                int min = int.MaxValue;
                int minIndex = -1;

                for (int v = 1; v <= vertexCount; v++)
                {
                    if (!visited[v] && distance[v] <= min)
                    {
                        min = distance[v];
                        minIndex = v;
                    }
                }
                return minIndex;
            }
        }

4단계: 시간 복잡도 분석

Dijkstra 알고리즘의 시간 복잡도는 O(V^2)입니다. 여기서 V는 정점의 수를 의미합니다.
따라서 정점의 수가 많은 경우, 더 효율적인 방법인 우선순위 큐를 사용한 개선된 Dijkstra 알고리즘을 고려할 수 있습니다.

마무리

이번 강좌에서는 C#을 사용하여 가장 빠른 버스 노선 구하기 문제를 해결하기 위해 Dijkstra 알고리즘을 구현해 보았습니다.
실제 코딩 테스트나 취업 면접에서 유사한 문제가 출제될 수 있으므로, 이 알고리즘을 충분히 이해하고 연습하는 것이 중요합니다.

앞으로도 다양한 알고리즘 문제와 해결 방법을 지속적으로 공부해 나가길 바랍니다. 추가로 궁금한 점이나 알고리즘 관련 문제는 언제든지 질문해 주세요!