[백준(BOJ)] 1753번 : 최단경로 - PYTHON[파이썬]

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 다익스트라

 

---

 

⊙ 문제 접근 과정

 

최단거리를 구하는 알고리즘 중 다익스트라를 사용해 문제를 풀었다.

다익스트라 함수를 만들 때, 시작값만 입력해주면 돌아가게끔 설계했다.

 

깔끔하게 3파트로 나누어 풀었다.

 

다익스트라 구현부, 입력부, 출력부

 

 

 

---

 

⊙ 문제 풀이

 

import sys
from heapq import heappush, heappop

input = sys.stdin.readline
INF = 1e9

# 다익스트라
def dijkstra(K):
    dp[K-1] = 0
    heappush(heap, [0, K-1])
    while heap:
        cost, pos = heappop(heap)
        for p, c in graph[pos]:
            c += cost
            if c < dp[p]:
                dp[p] = c
                heappush(heap, [c, p])


# 입력
V, E = map(int, input().split())
K = int(input())
graph = [[] for _ in range(V)]
dp = [INF]*V
heap = []
for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u-1].append([v-1, w])

dijkstra(K)

# 출력
for i in range(V):
    print("INF" if dp[i] == INF else dp[i])

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!