플로이드 [백준 11404] - python

import sys
input = sys.stdin.readline

def BOJ11404() :
  n = int(input())
  m = int(input())
  dist = [[1e9 for _ in range(n)] for _ in range(n)]
  for _ in range(m) :
    a, b, c = list(map(int, input().split()))
    dist[a - 1][b - 1] = min(dist[a-1][b-1], c)
  
  
  for k in range(n) :
    for i in range(n) :
      for j in range(n) :
        if dist[i][k] != 0 and dist[k][j] != 0 :
          dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
  
  for i in range(n) :
    for j in range(n) :
      if i != j :
        if dist[i][j] == 1e9 :
          print(0, end=' ')
        else :
          print(dist[i][j], end=' ')
      else :
        print(0, end=' ')
    print()

BOJ11404()

 

접근방법 :

1. 제목에도 나와있듯이 플로이드 워셜 알고리즘을 이용하면 된다.

2. 최단 거리를 구하는 알고리즘이 두개가 있다. 플로이드 워셜, 다익스트라 둘다 네트워크에서 라우터의 최단경로를 구하다가 탄생한 알고리즘이다. 

모든 점에서 각각의 점으로의 최단 거리를 구하고 싶을때는 플로이드 워셜 알고리즘을 쓰면 된다.

한 점에서 특정한 점으로의 최단 거리를 알고 싶다면 다익스트라 알고리즘을 사용하자.

3. pivot을 하나 잡고 [시작점][pivot] + [pivot][종료점]을 통해 최단거리를 계속 갱신해주자!!

 

 

 

 

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

11404번: 플로이드