문제
1번부터 N번까지의 노드가 있는데 중간에 소개팅녀를 만나는 노드를 거쳐야 한다
따라서 n번 노드를 가야한다면 중간에 소개팅녀가 있는 k번 노드를 지나야 한다는 것
각 노드 사이는 양방향으로 갈 수 있고 1의 cost를 가진다
플로이드 워셜 알고리즘
모든 지점에서 다른 모든 지점까지의 최단 경로 구하는 알고리즘
(cf. 다익스트라 - 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 알고리즘)
2차원 배열을 사용하여 각 노드에서 다른 노드로 가는 모든 최단 거리를 구해야함
-> O(N^2)의 시간 복잡도가 필요
방문판매원이 1번 노드에서 4번 노드까지 최단거리로 방문해야 한다면
- 1번에서 출발하여 2번 노드를 경유해서 4번 노드로 가는 경우
- 1번에서 출발하여 3번 노드를 경유해서 4번 노드로 가는 경우
두가지를 모두 고려하여 최단 거리를 구해주어야 함
이때, graph[1][3]은 1에서 3으로 가는 최단의 거리(cost)이기 때문에
- graph[1][2] + graph[2][4]
- graph[1][3] + graph[3][4]
이러한 형식으로 최단 거리를 표현할 수 있다.
경유를 하는 node들은 for문을 통해서 해결한다고 가정한다면 점화식은
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]
(1<=k<=n)
graph는 각 노드에서 각 노드로 가는 가장 짧은 거리라고 한다
via는 각 노드에서 각 노드로 가장 짧은 거리로 가기 위해서 거쳐야 하는 중간 노드
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
graph = [[INF]*(n+1) for i in range(0, n+1)]
via = [[0]*(n+1) for i in range(0, n+1)]
for i in range(1, n+1):
for j in range(1, n+1):
if i==j:
graph[i][j] = 0
via[i][j] = i
for _ in range(0, m):
a, b = map(int, input().split())
graph[a][b] = 1
graph[b][a] = 1
via[b][a] = a
via[a][b] = b
# k = 중간 방문 소개팅녀 회사 / x = 최종 계약 회사 / 판매원은 1번 회사
x, k = map(int, input().split())
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
if graph[i][k]+graph[k][j]<graph[i][j]:
graph[i][j] = graph[i][k]+graph[k][j]
via[i][j] = k경유할 경우에 가장 짧은 거리가 나올 때마다 그 때의 노드를 저장한 값이 via이기 때문에
역추적 하듯이 경로를 알아내면 된다
예를 들어 1->4번이면 1->4 direct로 가는 경우가 가장 짧으면 via[1][4]=4이겠지만
중간에 거쳐가는 node가 있다면 v[1][4] != 4일 것이다
따라서 아닌 목적지 노드가 via의 값이 아닌 경우에는 v[1][via]값으로 하여서 다시 살펴본다
결국 트리형식으로 분할해나가며 경로를 list에 append하는 방식
path = list()
def split(s, e):
if(via[s][e]==e):
path.append(s)
path.append(e)
else:
split(s, via[s][e])
path.pop()
split(via[s][e], e)
print(graph[1][k] + graph[k][x])
print(via)
print(1, end=" ")
split(1, k)
print()
split(k, x)
print(path)