문제
https://www.acmicpc.net/problem/1753
어떤 방향 그래프가 주어졌을 때, 시작점에서 다른 정점들로 이동할 수 있는 최단 거리를 구하는 문제이다.
주의할 점은 ✨두 정점 사이에 여러 간선이 존재할 수도 있다는 점이다.
문제 풀이
우선 방향그래프를 만들어준다.
graph = collections.defaultdict(list)
for _ in range(간선 개수):
# 출발지 u, 도착지 v, 비용 w
u, v, w = map(int,input().rstrip().rsplit())
graph[u].append((v,w))문제에서 주어진대로 시작 정점 k에서 다른 모든 정점까지 최단 거리를 구해야한다.
Q = [(0,k)]
dist = collections.defaultdict(int)따라서 Q에 (시작 비용, 시작 정점)을 넣어주었다.
dist 리스트에는 각 정점에 대한 최단 비용을 넣어줄 것이다.
while Q:
cnt, node = heapq.heappop(Q)
if node not in dist:
dist[node] = cnt
for v,w in graph[node]:
# temp : 현재 정점까지 오는데에 걸린 경로 + 가중치
temp = cnt + w
heapq.heappush(Q,(temp,v))Q에서 꺼낸 정점 node가 dist 리스트에 없으면, 그 정점으로 처음 방문하는 것이다.
따라서 dist[node] 에 cnt를 할당해준다.
이때 중요한 것은 우선순위 큐를 이용해서 node와 cnt를 꺼내주었다는 점이다.
파이썬의 우선순위 큐는 기본적으로 최소힙이다.
따라서 같은 node라는 정점이면, 더 작은 cnt 값이 먼저 꺼내진다.
🔥 그래서 같은 정점에 대해 여러 간선들이 있어도 최단 거리만을 고려할 수 있다.
그리고 정점 node와 연결된 다른 정점 v에 대해서도 방문을 해줄 것이다.
정점 node에서 정점 v로 이동할 때 드는 비용 w + node 까지 이동하는데 든 비용 cnt를 더해서 temp 변수에 담아준다.
그리고 Q에 (temp, 이동한 정점 v) 를 삽입해준다.
결과적으로 dist 리스트에는 k번 정점에서 i번째 인덱스로 이동하는 최단거리만이 저장된다.
만약 i가 시작점이 아닌데, dist[i]가 0이라면 이동할 수 없는 정점이 존재한다는 의미이므로 INF를 출력한다.
그 이외에는 dist[i]를 출력한다.
Q. dist[i]가 0인데 왜 이동할 수 없는 정점이죠?
dist 리스트를collections.defaultdict(int)로 만들어주었기 때문에 디폴트 값은 모두 0이다.
✨ 큐를 이용해서 연결된 정점을 모두 방문했음에도 값이 바뀌지 않았다는 것은 연결되지 않은 정점이 존재한다는 의미다.
코드
import sys
import collections
import heapq
input = sys.stdin.readline
# 정점 개수 v, 간선 개수 e, 시작정점 k
vc, ec = map(int,input().rstrip().rsplit())
k = int(input().rstrip())
graph = collections.defaultdict(list)
for _ in range(ec):
u, v, w = map(int,input().rstrip().rsplit())
graph[u].append((v,w))
Q = [(0,k)]
dist = collections.defaultdict(int)
while Q:
cnt, node = heapq.heappop(Q)
if node not in dist:
dist[node] = cnt
for v,w in graph[node]:
# temp : 현재 정점까지 오는데에 걸린 경로 + 가중치
temp = cnt + w
heapq.heappush(Q,(temp,v))
# dist 리스트에 저장된 가중치 값을 출력해준다
# 이때 시작점이 아닌데 가중치가 0인값은 경로가 존재하지 않는 경우이므로 INF를 출력한다.
for i in range(1,vc+1):
if dist[i]==0 and i!=k:
print("INF")
else:
print(dist[i])