[알고리즘] 플로이드 워셜 알고리즘

본 글은 나동빈 님의 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 참고하여 정리하였습니다.

플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)

[[최단 경로 알고리즘]]의 하나이다.

다익스트라 알고리즘은 "특정한 하나의 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우"에 사용할 수 있는 알고리즘이다. 플로이드 워셜 알고리즘은 "모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우"에 사용할 수 있는 알고리즘이다. 개념은 무척 간단하고 소스코드도 매우 짧지만, 핵심 아이디어를 이해하는 것이 중요하다.

플로이드 워셜 알고리즘은 다익스트라 알고리즘처럼 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다. 노드의 개수가 N개일 때 O(N^2)의 연산을 N번의 단계에 걸쳐 수행한다. 따라서 총시간 복잡도는 O(N^3)이다. N개의 노드 각각에 대해, O(N^2)의 연산 동안 "현재 노드를 거쳐가는 모든 경로"를 탐색한다.

모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문에, 2차원 리스트에 최단 거리 정보를 담을 필요가 있다. 노드의 개수가 N개일 때, N번의 단계를 반복하며 점화식에 맞게 2차원 리스트를 갱신하기 때문에, 플로이드 워셜 알고리즘은 다이나믹 프로그래밍으로 볼 수 있다.

백준 2617번: 구슬 찾기

기본적인 플로이드 워셜 알고리즘을 확인할 수 있는 문제이다. 현재 노드 k에 대해, k를 거쳐가는 모든 경로를 탐색하기 위해 O(N^2)의 연산을 수행한다. 코드 구현에서 어려울 것은 1도 없다. 사실 그냥 3중 for문이다. 플로이드 워셜 알고리즘은 일반적인 최단 경로 문제보다는 모든 경로를 구해야 하는 특수한 문제에서만 사용할 수 있을 것 같다.

전체 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [[False] * n for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    graph[a-1][b-1] = True

for k in range(n):
    for a in range(n):
        for b in range(n):
            if graph[a][k] and graph[k][b]:
                graph[a][b] = True

answer = 0
for i in range(n):
    if graph[i].count(True) > n//2:
        answer += 1
    col = [graph[j][i] for j in range(n)]
    if col.count(True) > n//2:
        answer += 1

print(answer)