코딩 테스트 대비: 플로이드-와샬 알고리즘 - 모든 정점 쌍의 최단 경로 찾기 (C#)

안녕하세요, GameLabMaster입니다! 이번 코딩 테스트 대비 포스팅에서는 그래프 알고리즘 중 플로이드-와샬(Floyd-Warshall) 알고리즘을 활용한 문제 풀이에 대해 알아보겠습니다. 플로이드-와샬 알고리즘은 모든 정점 쌍의 최단 경로를 찾는 알고리즘으로, 다익스트라 알고리즘과 함께 널리 사용됩니다.
 
문제
주어진 가중치 그래프에서 모든 정점 쌍의 최단 경로를 구하는 프로그램을 작성하세요.
 
입력

• 정점의 개수 N (1 ≤ N ≤ 100)
• 간선의 개수 M (0 ≤ M ≤ N*(N-1)/2)
• M개의 간선 정보. 각 간선은 세 개의 정수로 주어지며, 이는 시작 정점 u, 도착 정점 v, 가중치 w (1 ≤ u, v ≤ N, u ≠ v, 1 ≤ w ≤ 100)를 의미한다.

출력

• N개의 줄, 각 줄에 N개의 정수로, i번째 줄의 j번째 정수는 정점 i에서 정점 j까지의 최단 경로의 길이를 의미한다. (자기 자신으로의 경로는 항상 0이다)

풀이
플로이드-와샬 알고리즘은 다이나믹 프로그래밍 기법을 사용하여 각 정점 쌍의 최단 경로를 찾습니다. 이 알고리즘은 모든 정점 쌍에 대해 중간에 거치는 정점을 하나씩 추가해 가며 최단 경로를 갱신합니다.
 
다음은 C#으로 작성한 플로이드-와샬 알고리즘을 사용하여 모든 정점 쌍의 최단 경로를 구하는 코드입니다.
 

using System;

class Program {
    static void Main(string[] args) {
        int n = int.Parse(Console.ReadLine());
        int m = int.Parse(Console.ReadLine());
        int[,] dist = new int[n, n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) dist[i, j] = 0;
                else dist[i, j] = int.MaxValue / 2; // 무한대를 의미하는 큰 값으로 초기화
            }
        }

        for (int i = 0; i < m; i++) {
            string[] input = Console.ReadLine().Split(' ');
            int u = int.Parse(input[0]) - 1;
            int v = int.Parse(input[1]) - 1;
            int w = int.Parse(input[2]);
            dist[u, v] = w;
            dist[v, u] = w;
        }

        // 플로이드-와샬 알고리즘 수행
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dist[i, j] = Math.Min(dist[i, j], dist[i, k] + dist[k, j]);
                }
            }
        }

        // 출력
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                Console.Write(dist[i, j] + " ");
            }
            Console.WriteLine();
        }
    }
}

 
이 코드는 먼저 그래프를 인접 행렬로 표현한 후, 플로이드-와샬 알고리즘을 수행하여 모든 정점 쌍의 최단 경로를 구합니다. 최종 결과를 출력하기 전까지의 모든 과정은 O(N^3)의 시간 복잡도를 가지며, 플로이드-와샬 알고리즘은 이러한 시간 복잡도를 가지는 알고리즘 중 하나입니다.
 
이렇게 플로이드-와샬 알고리즘을 활용하여 문제를 해결할 수 있습니다. 이 기법을 익히면 다양한 그래프 관련 문제를 쉽게 해결할 수 있으므로, 코딩 테스트 대비에 도움이 될 것입니다. 여러분도 꼭 한 번 연습해보시기 바랍니다.
 
이번 포스팅에서는 플로이드-와샬 알고리즘에 대해 알아보았습니다. 다음 포스팅에서는 다른 알고리즘 문제와 그에 대한 풀이 방법을 소개하겠습니다.