백준 1753번 최단경로

정보

문제 바로가기 [클릭]

난이도: Gold5

관련 개념: #그래프 #다익스트라

---

조건

시간 제한	메모리 제한
1 초	256 MB

---

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

---

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

---

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

---

예제 입출력 1

입력

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

출력

0
2
3
7
INF

---

코드(파이썬)

import sys
import heapq


v, e = map(int, sys.stdin.readline().split())
start = int(sys.stdin.readline())

inf = 3000001
visited = set()
graph = dict()

d = [[inf, node] for node in range(1, v+1)]
d[start-1][0] = 0
queue = [d[start-1]]

for _ in range(e):
    n1, n2, w = map(int, sys.stdin.readline().split())
    if n1 in graph:
        if n2 in graph[n1]:
            graph[n1][n2] = min(w, graph[n1][n2])
        else:
            graph[n1][n2] = w
    else:
        graph[n1] = {n2: w}
        
while queue:
    mid_weight, mid = heapq.heappop(queue)
    visited.add(mid)

    if mid in graph:
        for end, weight in graph[mid].items():
            if end not in visited and d[end-1][0] > mid_weight + weight:
                d[end-1][0] = mid_weight + weight
                heapq.heappush(queue, (mid_weight + weight, end))

d.sort(key=lambda x: x[1])
sys.stdout.write('\n'.join(['INF' if w == inf else str(w) for w, _ in d]))

---

특이사항

• 이론만 배운 다익스트라 알고리즘의 첫 번째 실전 문제
  • 방문 정점 저장
  • 시작정점으로부터 최단거리를 저장할 리스트 d 생성
  • 리스트 d의 시작정점은 0, 나머지 정점은 적절한 INF으로 초기화
  • 다음 방문지를 (거리, 노드) 순으로 저장할 힙 queue 선언
  • queue에서 pop해 mid_weight와 mid에 저장
  • mid 노드에서 갈 수 있는 노드가 존재한다면 -> 그 노드 중 weight값을 업데이트할 노드가 있다면 -> 리스트 d 업데이트, queue에 저장

---

참고문헌

• 문병로, 쉽게 배우는 알고리즘 :관계 중심의 사고법, 문병로, 2018