[ BOJ 1753 ] 최단 경로(Python)

uoayop·2021년 3월 15일
0

알고리즘 문제

목록 보기
29/103
post-thumbnail

문제

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])
profile
slow and steady wins the race 🐢

0개의 댓글