[백준] 11404 - 플로이드

1. 문제

11404번: 플로이드

2. 개요

n개의 도시가 있고, 한 도시에서 출발해 다른 도시에 도착하는 m대의 버스와 그 비용이 주어질 때, 모든 도시 쌍에 대한 비용의 최솟값을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

모든 정점에서 모든 정점에 대한 최소거리를 구하는 문제이므로 플로이드 워셜 알고리즘을 이용.

입력 받을 때, 같은 경로이지만 비용이 다른 경우가 있기 때문에 항상 최솟값으로 갱신하는 것과 경로가 없는 경우 0으로 출력한다는 점만 주의하면 된다.

3-2. Python

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

graph = [[10000000000 for i in range(n)] for j in range(n)]

for i in range(n):
    graph[i][i] = 0

for i in range(m):
    start, end, cost = map(int, sys.stdin.readline().split())

    if graph[start-1][end-1] > cost:
        graph[start-1][end-1] = cost

for m in range(n):
    for s in range(n):
        for e in range(n):
            if graph[s][e] > graph[s][m] + graph[m][e]:
                graph[s][e] = graph[s][m] + graph[m][e]

for i in range(n):
    for j in range(n):
        if graph[i][j] == 10000000000:
            print(0, end= ' ')
        else:
            print(graph[i][j], end = ' ')

    print()

3-3. C#

namespace boj_11404
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int m = int.Parse(Console.ReadLine());

            long[,] graph = new long[n, n];

            for (int i = 0; i < graph.GetLength(0); i++)
            {
                for (int j = 0; j < graph.GetLength(1); j++)
                {
                    if (i == j)
                        graph[i, j] = 0;
                    else
                        graph[i, j] = 10000000000;

                }
            }

            for (int i = 0; i < m; i++)
            {
                string[] input = Console.ReadLine().Split();
                int start = int.Parse(input[0]) - 1;
                int end = int.Parse(input[1]) - 1;
                int cost = int.Parse(input[2]);

                if (graph[start, end] > cost)
                    graph[start, end] = cost;
            }

            for (int mid = 0; mid < n; mid++)
            {
                for (int s = 0; s < n; s++)
                {
                    for (int e = 0; e < n; e++)
                    {
                        if (graph[s, e] > graph[s, mid] + graph[mid, e])
                            graph[s, e] = graph[s, mid] + graph[mid, e];
                    }
                }
            }

            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    long tmp = graph[i, j] == 10000000000 ? 0 : graph[i, j];
                    Console.Write($"{tmp} ");
                }
                Console.WriteLine();
            }

        }
    }
}