코딩 테스트 대비: 다익스트라 알고리즘을 이용한 최단 경로 찾기(C#)

안녕하세요, GameLabMaster입니다! 오늘의 코딩 테스트 대비 포스팅에서는 다익스트라 알고리즘을 이용한 최단 경로 찾기 문제를 다루겠습니다. 다익스트라 알고리즘은 그래프의 한 정점에서 다른 정점으로 가는 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 음의 가중치가 없는 그래프에서 사용할 수 있습니다.

 

문제
주어진 가중치 그래프에서 시작 정점에서 다른 정점으로 가는 최단 경로를 구하세요.

예시: 입력:

 

그래프:
    0 --1-- 1 --1-- 2
     \      \
      \      \
       4      2
        \      \
         \      \
          3 --1-- 4

 

출력:

 

최단 경로:
0 -> 1: 거리 1
0 -> 2: 거리 2
0 -> 3: 거리 4
0 -> 4: 거리 3

 

풀이
다음과 같은 단계로 다익스트라 알고리즘을 구현할 수 있습니다.

1. 시작 정점에서 각 정점까지의 거리를 저장하는 배열을 생성하고, 모든 값을 무한대로 초기화합니다. 시작 정점의 거리는 0으로 설정합니다.
2. 처리되지 않은 정점 중 거리가 가장 작은 정점을 선택합니다.
3. 선택한 정점을 기준으로 인접한 정점들의 거리를 갱신합니다.
4. 모든 정점이 처리될 때까지 2-3단계를 반복합니다.

 

먼저, 그래프를 표현하기 위해 인접 리스트를 사용하여 표현하겠습니다. 인접 리스트는 각 정점의 인접한 정점과 가중치를 저장하는 리스트로 구성됩니다.

 

public class Edge {
    public int To { get; set; }
    public int Weight { get; set; }

    public Edge(int to, int weight) {
        To = to;
        Weight = weight;
    }
}

public static List<List<Edge>> BuildGraph() {
    List<List<Edge>> graph = new List<List<Edge>> {
        new List<Edge> { new Edge(1, 1), new Edge(3, 4) }, // 정점 0의 인접 리스트
        new List<Edge> { new Edge(0, 1), new Edge(2, 1), new Edge(4, 2) }, // 정점 1의 인접 리스트
        new List<Edge> { new Edge(1, 1) }, // 정점 2의 인접 리스트
        new List<Edge> { new Edge(0, 4), new Edge(4, 1) }, // 정점 3의 인접 리스트
        new List<Edge> { new Edge(1, 2), new Edge(3, 1) } // 정점 4의 인접 리스트
    };
    return graph;
}

 

이제 다익스트라 알고리즘을 구현해보겠습니다.

 

public static int[] Dijkstra(List<List<Edge>> graph, int start) {
    int[] distances = new int[graph.Count];
    bool[] visited = new bool[graph.Count];

    for (int i = 0; i < graph.Count; i++) {
        distances[i] = int.MaxValue;
    }
    distances[start] = 0;

    for (int i = 0; i < graph.Count; i++) {
        int closestVertex = -1;
        int closestDistance = int.MaxValue;

        for (int j = 0; j < graph.Count; j++) {
            if (!visited[j] && distances[j] < closestDistance) {
                closestVertex = j;
                closestDistance = distances[j];
            }
        }

        visited[closestVertex] = true;

        foreach (Edge edge in graph[closestVertex]) {
            int newDistance = closestDistance + edge.Weight;
            if (newDistance < distances[edge.To]) {
                distances[edge.To] = newDistance;
            }
        }
    }

    return distances;
}

 

이제 주어진 그래프를 생성하고 다익스트라 알고리즘을 호출하여 최단 경로를 출력해보겠습니다.

 

public static void Main(string[] args) {
    List<List<Edge>> graph = BuildGraph();
    int[] distances = Dijkstra(graph, 0);

    Console.WriteLine("최단 경로: ");
    for (int i = 1; i < distances.Length; i++) {
        Console.WriteLine("0 -> " + i + ": 거리 " + distances[i]);
    }
}

 

위 예제에서는 주어진 그래프를 생성하고 Dijkstra 메서드를 호출하여 시작 정점에서 다른 정점으로 가는 최단 경로를 구한 뒤 출력하였습니다. 실행 결과, 주어진 그래프에서 시작 정점에서 다른 정점으로 가는 최단 경로가 올바르게 출력됩니다.

 

이상으로 오늘의 코딩 테스트 대비 포스팅을 마치겠습니다. 다음 포스팅에서도 더 유용한 정보를 드릴 것입니다. 그럼, 즐거운 코딩 되세요!