[알고리즘 문제 풀기] 플로이드(11404)

1. 문제 풀이 아이디어

• 플로이드-워셜 알고리즘을 사용하여 모든 정점 간 최단 거리를 구해 문제를 해결할 수 있다.

2. 나의 정답 코드

using System.Text;
StringBuilder sb = new StringBuilder("");

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int n = int.Parse(sr.ReadLine());
    int m = int.Parse(sr.ReadLine());
    int[,] map = new int[n + 1, n + 1];
    for (int i = 0; i < m; i++)
    {
        string[] split = sr.ReadLine().Split();
        int a = int.Parse(split[0]);
        int b = int.Parse(split[1]);
        int c = int.Parse(split[2]);
        map[a, b] = map[a, b] == 0 ? c : Math.Min(map[a, b], c);
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= n; k++)
            {
                if (j == k || map[j, i] == 0 || map[i, k] == 0) continue;
                int dist = map[j, i] + map[i, k];
                map[j, k] = map[j, k] == 0 ? dist : Math.Min(map[j, k], dist);
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            sb.Append($"{map[i, j]} ");
        }
        sb.AppendLine();
    }
    sw.WriteLine(sb);
}

3. 정리

• map[i, j]는 i에서 j로 가는 최소 비용을 저장한다.

• 간선 정보를 입력받을 때, 중복 간선이 존재하면 최소 비용으로 갱신한다.

• 플로이드-워셜 알고리즘을 적용하여 모든 정점 간 최단 거리를 구한다.

• i를 거쳐 j → k로 이동하는 경로를 고려하여 더 짧은 거리가 발견되면 갱신한다.