문제
n(1 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.
모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.
시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.
출력
n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.
코드
#include <iostream> #include <algorithm> using namespace std; int N, M; int Map[101][101]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> N >> M; for (int i = 0; i < M; ++i) { int from, to, cost; cin >> from >> to >> cost; // 플로이드-와샬 알고리즘은 그래프 상에서 // 모든 노드에서 모든 노드로의 최단 거리를 // 구하는 알고리즘이다. // 현재까지의 최단 경로를 구한다. if (Map[from][to]) Map[from][to] = min(Map[from][to], cost); else Map[from][to] = cost; } // 핵심은 다른 노드를 거쳤을 때, // 비용이 더 싼지 확인하는 것이다. for (int via = 1; via <= N; ++via) { for (int from = 1; from <= N; ++from) { for (int to = 1; to <= N; ++to) { if (Map[from][via] == 0 || Map[via][to] == 0 || from == to) continue; if (Map[from][to] == 0 || Map[from][via] + Map[via][to] < Map[from][to]) Map[from][to] = Map[from][via] + Map[via][to]; } } } for (int r = 1; r <= N; ++r) { for (int c = 1; c <= N; ++c) cout << Map[r][c] << ' '; cout << '\n'; } } |
using System; using System.Collections.Generic; namespace Csharp { class Program { static int N, M; static int[,] Map = new int[101, 101]; static void Main(string[] args) { N = Convert.ToInt32(Console.ReadLine()); M = Convert.ToInt32(Console.ReadLine()); for (int i = 0; i < M; ++i) { int from, to, cost; var inputs = Console.ReadLine().Split(); from = Convert.ToInt32(inputs[0]); to = Convert.ToInt32(inputs[1]); cost = Convert.ToInt32(inputs[2]); if (Map[from, to] == 0) Map[from, to] = cost; else Map[from, to] = Math.Min(Map[from, to], cost); } for (int via = 1; via <= N; ++via) { for (int from = 1; from <= N; ++from) { for (int to = 1; to <= N; ++to) { if (Map[from, via] == 0 || Map[via, to] == 0 || from == to) continue; if (Map[from, to] == 0 || Map[from, to] > Map[from, via] + Map[via, to]) Map[from, to] = Map[from, via] + Map[via, to]; } } } for (int r = 1; r <= N; ++r) { for (int c = 1; c <= N; ++c) Console.Write($"{Map[r, c]} "); Console.WriteLine(); } } } } |
from sys import stdin, setrecursionlimit input = stdin.readline N = int(input()) M = int(input()) Graph = [ [0] * (N + 1) for i in range(N + 1) ] for i in range(M): s, e, w = map(int, input().split()) if Graph[s][e] == 0 or Graph[s][e] > w: Graph[s][e] = w for via in range(1, N + 1): for s in range(1, N + 1): for e in range(1, N + 1): if Graph[s][via] == 0 or Graph[via][e] == 0 or s == e: continue if Graph[s][e] == 0 or Graph[s][e] > Graph[s][via] + Graph[via][e]: Graph[s][e] = Graph[s][via] + Graph[via][e] for r in range(1, N + 1): for c in range(1, N + 1): print(Graph[r][c], end = ' ') print() |
복기
플로이드-와샬 알고리즘은 그래프에 있는 모든 정점에서 모든 정점으로의 최단 거리를 구하는 것이며, 임의로 선택한 두 노드 A, B에 대해 Dist(A, B)와 Dist(A, via) + Dist(via, B)를 비교하는 알고리즘이다.
Python3에서 0으로 초기화 된 리스트를 만들 때, [ 0 ] * N 하는 형식으로 만들곤 했는데, 다차원 배열에서는 리스트의 중복이 일어나므로 List Comprehension을 적용해야 한다.