11404: 플로이드

풀이 시간

• 11m
• 이번 삼성 SW 알고리즘 역량 강화 사전문제에 풀로이드 워셜 문제가 나왔는데, 플로이드 워셜 알고리즘에 대해 공부 좀 할겸 품

구현 방식

• 플로이드 워셜 알고리즘: 그래프 내의 모든 정점 쌍 간의 최단 경로를 구할 때 사용 (Dynamic Programming 기법) -> 그래프의 크기가 N일 때, O(N^3)의 시간복잡도
• a -> b로 바로 가는 것보다 a->k->b처럼 k를 거쳐 가는 게 효율적일 경우 해당 값을 갱신해주는 방식임 (k는 하나 이상)
• 점화식은 아래와 같음

  distance[a][b] = min(distance[a][b], distance[a][k] + distance[k][b])

• 3중 for문을 돌면서 최솟값을 갱신해줌 (k가 가장 상위 단계의 for문이어야함)

코드

import sys


N = int(input()); M = int(input())
distance = [[int(10e9) for _ in range(N+1)] for _ in range(N+1)]

for m in range(M):
    a, b, c = map(int, sys.stdin.readline()[:-1].split())
    distance[a][b] = min(c, distance[a][b]) #시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있음!

for k in range(1, N+1):
    for a in range(1, N+1):
        for b in range(1, N+1):
            if a == b:
                distance[a][b] = 0
            else:
                distance[a][b] = min(distance[a][b], distance[a][k] + distance[k][b])

for a in range(1, N+1):
    for b in range(1, N+1):
        if distance[a][b] == int(10e9):
            print(0, end=" ")
        else:
            print(distance[a][b], end=" ")
    print()

결과