[11404] - 플로이드

https://www.acmicpc.net/problem/11404

11404번: 플로이드

플로이드 워셜 알고리즘

모든 정점에서 다른 정점까지의 최단거리

- 다익스트라는 한(시작) 정점에서 다른 모든 정점까지의 최단 거리

 

문제 풀이

• 배열 생성 - 인덱스가 [시작, 도착] = 가중치
• 문제의 정점 개수가 100개, 가중치가 최대 100000이니 inf 는 10000000으로 설정
• 자기 자신을 탐색하는 경우는 거리(가중치)가 0이니 아닌 경우만 inf로 설정
• 입력에 '시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.' 라고 써있으니 입력을 받을 때 중복된 노선이 나오면 최소값으로 설정.
• 거치는 곳, 시작, 도착 순으로 3중 반복문을 만들어 시작 → 거침 + 거침 → 도착과 시작 → 도착을 비교하여 최소값 넣어주기.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;


namespace Baekjoon.Gold
{
    internal class _11404
    {
        const int inf = 10000000;

        static void Main(string[] args)
        {
            StringBuilder stb = new StringBuilder();
            int n = int.Parse(Console.ReadLine());
            int m = int.Parse(Console.ReadLine());
            //arr[시작, 도착] = 가중치
            int[,] arr = new int[n + 1, n + 1];

            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    //자기 자신은 0, 나머지는 inf로
                    if (i != j)
                        arr[i, j] = inf;
                }
            }

            for (int i = 0; i < m; i++)
            {
                int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                //중복되면 최소값으로
                arr[input[0], input[1]] = Math.Min(arr[input[0], input[1]], input[2]);
            }

            //플로이드 워셜
            for (int i = 1; i <= n; i++) //거치는 노드
            {
                for (int j = 1; j <= n; j++) // 시작 노드
                {
                    if (i == j)
                        continue;

                    for (int k = 1; k <= n; k++) // 끝 노드
                        arr[j, k] = Math.Min(arr[j, i] + arr[i, k], arr[j, k]);
                }
            }

            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    if (arr[i, j] == inf || i == j)
                        stb.Append("0 ");
                    else
                        stb.Append(arr[i, j].ToString()+" ");
                }
                stb.AppendLine();
            }

            Console.WriteLine(stb);
        }
    }
}