[백준 11404] 플로이드 (C#, C++) - soo:bak

문제 링크

11404번 - 플로이드

설명

도시와 버스 노선 정보가 주어지는 상황에서, 도시의 개수 n (1 ≤ n ≤ 100), 버스 노선의 개수 m (1 ≤ m ≤ 100,000), 그리고 각 노선의 정보(시작 도시, 도착 도시, 비용 1~100,000)가 주어질 때, 모든 도시 쌍에 대한 최소 이동 비용을 구하는 문제입니다.

같은 시작·도착 도시 쌍에 여러 개의 노선이 있을 수 있으며, 경로가 없는 경우 0을 출력합니다.

접근법

모든 도시 쌍에 대한 최단 경로를 구해야 하므로 플로이드-워셜(Floyd-Warshall) 알고리듬을 사용합니다.

플로이드-워셜 알고리즘은 동적 프로그래밍 기반으로, 중간 경유지를 하나씩 추가하며 모든 쌍의 최단 거리를 갱신합니다.

먼저 거리 행렬을 초기화합니다. 자기 자신으로 가는 거리는 0, 나머지는 무한대로 설정한 후, 입력으로 주어진 간선 정보를 반영합니다. 같은 시작·도착 쌍에 여러 노선이 있을 수 있으므로 더 작은 비용만 유지합니다.

k번 도시를 중간 경유지로 사용하는 경우를 모든 도시 쌍 (i, j)에 대해 확인합니다. i에서 k로, k에서 j로 가는 경로가 모두 존재할 때, i에서 k를 거쳐 j로 가는 비용이 현재 알고 있는 i에서 j로 가는 비용보다 작으면 갱신합니다.

모든 k에 대해 이 과정을 반복하면 최종적으로 모든 쌍의 최단 거리가 구해집니다.

세 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n³)이며, n이 최대 100이므로 충분히 빠릅니다.

---

Code

C#

using System;
using System.Text;

namespace Solution {
  class Program {
    const int INF = 1_000_000_000;

    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var m = int.Parse(Console.ReadLine()!);

      var dist = new int[n, n];
      for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++)
          dist[i, j] = i == j ? 0 : INF;
      }

      for (var i = 0; i < m; i++) {
        var input = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
        var start = input[0] - 1;
        var end = input[1] - 1;
        var cost = input[2];
        if (cost < dist[start, end])
          dist[start, end] = cost;
      }

      for (var k = 0; k < n; k++) {
        for (var i = 0; i < n; i++) {
          if (dist[i, k] == INF) continue;
          for (var j = 0; j < n; j++) {
            if (dist[k, j] == INF) continue;
            var newDist = dist[i, k] + dist[k, j];
            if (newDist < dist[i, j])
              dist[i, j] = newDist;
          }
        }
      }

      var result = new StringBuilder();
      for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++) {
          result.Append(dist[i, j] == INF ? 0 : dist[i, j]);
          if (j + 1 < n) result.Append(' ');
        }
        result.Append('\n');
      }
      Console.Write(result.ToString());
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

const int INF = 1e9;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  vvi dist(n, vi(n, INF));
  for (int i = 0; i < n; i++)
    dist[i][i] = 0;

  for (int i = 0; i < m; i++) {
    int start, end, cost;
    cin >> start >> end >> cost;
    start--; end--;
    dist[start][end] = min(dist[start][end], cost);
  }

  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      if (dist[i][k] == INF) continue;
      for (int j = 0; j < n; j++) {
        if (dist[k][j] == INF) continue;
        int newDist = dist[i][k] + dist[k][j];
        if (newDist < dist[i][j])
          dist[i][j] = newDist;
      }
    }
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cout << (dist[i][j] == INF ? 0 : dist[i][j]);
      if (j + 1 < n) cout << " ";
    }
    cout << "\n";
  }
  
  return 0;
}