Graph - 플로이드-워셜

1. 플로이드-워셜

1) 개념

지난 포스팅에서 배운 다익스트라와 벨만-포드는 특정 노드로부터 다른 모든 노드까지의 최단 거리를 구하는 One-to-Many 알고리즘이었다. 반면, 플로이드-워셜 알고리즘은 모든 노드 쌍에 대해 최단 거리를 구하는 Many-to-Many 알고리즘이다. 플로이드-워셜 알고리즘의 특징은 아래와 같다.

• 가중치가 음수인 간선이 존재하는 그래프에서도 사용할 수 있다. 단, 음수 사이클이 존재하는 경우에 대해서는 적용할 수 없다. (음수 사이클 존재 시, 벨만-포드 알고리즘을 사용해야 한다.)
• 최단 거리를 구하기 위해 2차원 배열과 동적 계획법을 사용한다.

플로이드-워셜 알고리즘에서는 최단 거리 배열로 2차원 배열을 사용한다. 이는 특정 노드에서 다른 모든 노드로의 최단 거리를 구할 때 1차원 배열을 사용하던 원리를, 모든 노드로 확장하겠다는 의미이다.

또한, 플로이드-워셜 알고리즘의 핵심 원리는 동적 계획법에 기반을 두고 있다. 예를 들어 아래의 그림과 같은 그래프가 있다고 하자. 1번 노드에서 5번 노드까지의 최단 경로를 구했다고 가정할 때, 최단 경로 위의 노드 K(= 3 or 4 or 2) 에 대해 1번 → K번, K번 → 5번까지의 경로 역시 최단 경로가 된다.

이와 같이 큰 문제의 최적해가 작은 하위 문제들의 최적해로 이루어지는 경우, 동적 계획법으로 풀이할 수 있다. 이 때, 사용되는 점화식은 D[S][E] = min(D[S][E], D[S][K] + D[K][E])로, 전체 경로의 최단 경로는 부분 경로의 최단 경로로 구성된다는 의미를 가진다.

2) 원리

① 최단 거리 리스트 초기화하기

• S와 E가 동일한 칸은 0으로, 나머지 칸은 ∞으로 초기화한다.

② 최단 거리 리스트에 그래프 데이터 저장하기

• 최단 거리 리스트가 2차원 배열이므로, 그래프를 인접 행렬로 표현해야 한다.

③ 점화식을 이용해 리스트 업데이트하기

• 아래와 같은 3중 for 문의 형태로 리스트의 값을 업데이트한다.

for k in range(1, N + 1): # 중간 노드
	for i in range(1, N + 1): # 출발 노드
    	for j in range(1, N + 1): # 도착 노드
        	dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

노드의 개수에 비례한 3중 for문을 사용한다는 점에서 플로이드-워셜 알고리즘의 시간 복잡도는 O(V^3)이 된다. 이러한 이유로, 플로이드-워셜 알고리즘을 요구하는 문제는 노드 개수의 범위가 매우 적을 수 밖에 없다.

3) 3중 for 문의 순서

3중 for 문의 순서를 임의로 변경하면 어떻게 될까? 결론부터 이야기하면, 3중 for 문의 순서는 변경이 불가하며, 반드시 중간 노드 > 출발 노드 > 도착 노드 순으로 구성해야 한다. 그 이유에 대해서는 동적 계획법의 개념을 통해 이해해보기로 하자.

동적 계획법은 점진적 개선 과정으로 이해할 수 있다. 즉, 가장 바깥 쪽의 for 문의 각 루프마다, 최적의 값이 점진적으로 개선된다는 것이다. 플로이드-워셜 알고리즘에서 최단 경로는 K 노드에 의해 업데이트 되는 것이므로, 당연히 가장 바깥 쪽 for 문에서 K 노드를 순회해야 할 것이다.

만약 출발 노드 > 도착 노드 > 중간 노드 또는 출발 노드 > 중간 노드 > 도착 노드의 순으로 for 문을 구성할 경우, 가장 바깥 쪽의 for 문에서 점진적 개선이 발생할 수 없게 되므로 결과적으로 최단 경로를 구할 수 없게 된다. 그러므로 3중 for 문의 순서가 변경되지 않도록, 3중 for 문의 순서를 암기해둘 것을 권장한다.

2. 문제 풀이

1) 가장 빠른 버스 노선 구하기

>> 백준 11404번

100개 이하의 노드에 대해 모든 노드 쌍의 최단 거리를 구하는 문제이므로, 플로이드-워셜 알고리즘을 이용하여 풀이할 수 있다.

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())

# 최단 거리 리스트 초기화
dist = [[sys.maxsize for i in range(n + 1)] for j in range(n + 1)]
for i in range(1, n + 1):
    dist[i][i] = 0

# 최단 거리 리스트에 그래프 데이터 저장
for i in range(m):
    u, v, w = map(int, input().split())
    dist[u][v] = min(dist[u][v], w) # 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다는 조건 때문

# 플로이드-워셜
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])


for i in range(1, n + 1):
    for j in range(1, n + 1):
        if dist[i][j] == sys.maxsize:
            print(0, end=' ')
        else:
            print(dist[i][j], end=' ')
        
    print() # 줄바꿈

2) 경로 찾기

>> 백준 11403번

이 문제도 플로이드-워셜 알고리즘을 사용하는 문제라는 사실을 쉽게 알 수 있다. 단, 최단 거리를 구할 필요는 없기 때문에, 이 부분은 연결 여부를 확인하는 로직으로 변경해주어야 한다.

import sys
input = sys.stdin.readline

N = int(input())

# 최단 거리 리스트 초기화
dist = [[0 for i in range(N)] for j in range(N)]

# 최단 거리 리스트에 그래프 데이터 저장
for i in range(N):
    lst = list(map(int, input().split()))
    for j in range(N):
        dist[i][j] = lst[j]

# 플로이드-워셜
for k in range(N):
    for i in range(N):
        for j in range(N):
            # 최단 거리를 구할 필요 없이 연결 여부만 확인하면 됨.
            if dist[i][k] == 1 and dist[k][j] == 1:
                dist[i][j] = 1

for i in range(N):
    for j in range(N):
        print(dist[i][j], end=' ')
    print()

3) 케빈 베이컨의 6단계 법칙

>> 백준 1389번

각 노드 간의 베이컨 수를 구해야 한다는 내용만 놓고 보았을 때는 BFS를 이용한 풀이를 떠올리기 쉽다.

import sys
input = sys.stdin.readline
from collections import deque

N, M = map(int, input().split())
graph = [[] for i in range(N + 1)]

for i in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

deq = deque()

def bfs(V):
    deq.append(V)
    visited[V] = 0

    while deq:
        V = deq.popleft()

        for i in graph[V]:
            if visited[i] == -1:
                deq.append(i)
                visited[i] = visited[V] + 1

Min = sys.maxsize
idx = 0
for i in range(1, N + 1):
    visited= [-1] * (N + 1)
    bfs(i)
    if Min > sum(visited) + 1:
        Min = sum(visited) + 1
        idx = i

print(idx)

물론, BFS를 이용한 풀이도 가능하지만, N이 충분히 적다는 점에서 플로이드-워셜 알고리즘을 사용하여 풀이할 수도 있을 것으로 판단된다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

# 최단 거리 리스트 초기화
dist = [[sys.maxsize for i in range(N + 1)] for j in range(N + 1)]
for i in range(1, N + 1):
    dist[i][i] = 0

# 최단 거리 리스트에 그래프 데이터 저장
for _ in range(M):
    s, e = map(int, input().split())
    dist[s][e] = 1
    dist[e][s] = 1 # 무향 그래프

# 플로이드-워셜
for k in range(1, N + 1):
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Min = sys.maxsize
result = -1

for i in range(1, N + 1):
    temp = 0
    for j in range(1, N + 1):
        temp += dist[i][j]
    if Min > temp: # 최소 값이 여러 개일 경우 가장 낮은 인덱스 출력
        Min = temp
        result = i

print(result)