백준 11404번: 플로이드

✔ 풀이를 위한 아이디어

• 그래프 (Graph) 이론

• 플로이드-와샬 (Floyd–Warshall) 알고리즘 (모든 지점에서 다른 모든 지점까지의 최단 경로)
  
  

✔ 알고리즘 설명

• 플로이드-와샬 알고리즘을 공부한 뒤에 코드를 짜보았다.

• https://www.youtube.com/watch?v=hw-SvAR3Zqg 의 알고리즘 설명부분만 참고하였다.

플로이드-와샬 알고리즘 개요

• 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산하는 알고리즘이다.

• 다익스트라 알고리즘과 다르게 최단거리를 갖는 노드를 찾는 과정이 필요 없다. (다익스트라 알고리즘에서는 이를 구현하기 위해서 최소 힙을 사용하였다.)

• 3중 for문을 돌며 2차원 테이블에 최단거리 정보를 저장하는 방식으로 구현한다. (다익스트라 알고리즘은 한 지점에서 다른 모든 지점만 구하면 됐으므로 1차원 배열을 사용했다.)

• 이는 다이나믹 프로그래밍 유형에 속한다. 왜냐하면 노드의 개수 N번 만큼 반복하며 '점화식에 맞게' 2차원 배열을 갱신하기 때문이다. (다익스트라 알고리즘은 그리디 알고리즘에 속한다.)

• 다익스트라 알고리즘보다 구현 난이도는 낮은 편에 속하며, 시간복잡도가 O(N^3)이므로 노드 및 간선의 개수가 적을 때 사용한다.

알고리즘 동작 과정

• 2차원 테이블을 초기화 한다. (갈 수 없는 경우는 거리를 INF로 설정하고, 자신으로부터 자신으로까지의 거리는 0으로 설정한다.)

• 노드가 4개라면, 자신을 제외한 나머지 3개 중에서 2개를 고르는 경우의 수만큼 갱신한다. 이때, 자신이 시작점이나 끝점에 있는 경우를 제외하며, 대각선 상에 있는 거리가 0인 경우도 제외한다.

• 갱신을 할 때에는 기본 점화식에 의해서, 기존에 테이블에 있던 값과 현재 검토 중인 노드를 거쳐갈 때의 값을 비교한다.

플로이드-와샬 알고리즘의 기본 점화식

• 위의 과정을 노드의 개수만큼 반복한다.

✔ 전체 코드

import sys

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

INF = float('inf')
table = [[INF]*n for _ in range(n)]  # 무한대로 초기화

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    if table[a-1][b-1] == INF:
        table[a-1][b-1] = c
    else:  # 기존에 값이 있다면 최솟값만 남기기
        table[a-1][b-1] = min(table[a-1][b-1], c)

for i in range(n):
    table[i][i] = 0  # 자신에서 자신으로 가는 경우는 0으로 초기화

for current in range(n):
    for start in range(n):
        for end in range(n):
            if start == current or end == current or start == end:  # 갱신할 필요 없는 경우
                continue
            table[start][end] = min(table[start][end], table[start][current] + table[current][end])
            # 기본 점화식에 따른 갱신, y축 방향으로 시작 지점들이 있고 x축 방향으로 도착 지점들이 있다.

for start in range(n):
    for end in range(n):
        if table[start][end] == INF:  # 갈 수 없는 경우 0을 출력
            print("0 ", end="")
        else:
            print("{} ".format(table[start][end]), end="")
    print()

• 마지막 부분에 INF 값의 출력을 0으로 처리해주지 않아서 한 차례 '틀렸습니다' 를 받았다.
  
  

이 알고리즘 역시 오랫동안 쓰지 않으면 까먹을 수 있으므로, 반드시 복습하도록 하자!