링크 : https://www.acmicpc.net/problem/1719
1719번: 택배
명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하
www.acmicpc.net
코드
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의 첫 번째 원소가 같기 때문이다.
'알고리즘 > BAEKJOON (Python)' 카테고리의 다른 글
[ 백준 / 골드2 / 파이썬 Python ] 1365번 - 꼬인 전깃줄 (0) | 2023.04.11 |
---|---|
[ 백준 / 골드2 / 파이썬 Python ] 2233번 - 사과나무 (0) | 2023.04.11 |
[ 백준 / 골드4 / 파이썬 Python ] 1647번 - 도시 분활 계획 (0) | 2023.04.10 |
[ 백준 / 실버2+골드1 / 파이썬 Python ] 2098번 - 외판원 순회 (0) | 2023.04.10 |
[ 프로그래머스 / LV2 / 파이썬 Pyhton ) 마법의 엘리베이터 (0) | 2023.04.06 |