[ 백준 / 골드3 / 파이썬 Python ] 1719번 - 택배

링크 : https://www.acmicpc.net/problem/1719

1719번: 택배

 

코드

---

n,m = map(int,input().split())
graph = [[1e9]*(n+1) for _ in range(n+1)]
dp = [[str(x)]*(n+1) for x in range(n+1)]

for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a][b] = c
    graph[b][a] = c
    dp[a][b] = b
    dp[b][a] = a

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if graph[i][j] > graph[i][k]+graph[k][j]:
                graph[i][j] = graph[i][k]+graph[k][j]
                dp[i][j] = dp[i][k]

for i in range(1,n+1):
    dp[i][i] = "-"

for x in dp[1:]:
    print(*x[1:])

 

풀이

---

한 점에서 다른 점까지 최단경로로 이동할 때, 그 경로의 첫 번째 방문노드를 출력하는 문제이다.

처음에는 최단경로자체를 저장한 후에 가장 첫 노드만 따로 빼서 출력했는데 이상하게 8%에서 틀려서 첫 노드만 저장하는 것으로 바꾸었다.

 

모든 점에서 모든 노드로의 최단 경로를 찾아야 하므로 "플로이드 워샬" 알고리즘을 사용했다.

n이 200까지 올라가므로 시간복잡도는 O(n*3 = 800만)으로 2초안에 충분히 해결가능하다. 평소의 플로이드 워샬처럼 진행하나 dp테이블 하나가 추가된다. dp[x][y]는 x에서 y까지의 최단경로에서의 첫번째 방문노드를 의미한다.

a와 b가 연결되고 c라는 가중치가 있다. 입력까지만 놓고 본다면 a에서 b까지의 최단경로는 a-b이고 첫번째원소는 b이다.

이런 방식으로 들어오는 간선에 대한 정보를 모두 저장한다.

 

이제 플로이드 워샬의 방식대로 최단경로를 구하는데 탐색하다 만약 x->y의 경로가 최단경로로 갱신된다면 dp[x][y]는 dp[x][k]로 바꾸어 준다. 왜냐하면 x->y로 가는 최단경로는 x->k->y와 같고 따라서 x->k의 경로의 첫 번째 원소와 x->y의 첫 번째 원소가 같기 때문이다.