[Baekjoon Online Judge] 백준 1753번 최단경로(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1753번 최단경로

(Python)

(글쓴날 : 2020.06.09)

 

---

* Baekjoon Online Judge, 백준 1753번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1753번 최단경로

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1753

1753번: 최단경로

---

2) 풀이 과정

* 시간 복잡도 : O(E log V)

 

방향 그래프와 시작점이 주어질 때, 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 문제입니다.

 

저의 경우, 다익스트라를 적용하였고, Python을 사용했습니다.

우선, 문제에서 주어지는 정점, 간선, 가중치를 인접 리스트로 구현한 뒤, 시작점에 다익스트라를 적용하여 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys, heapq
input = sys.stdin.readline
 
def BFS(hq):
    global distance
 
    while(hq):
        wei, vec = heapq.heappop(hq)
 
        if distance[vec] > wei:
            distance[vec] = wei
 
            for v, w in adjList[vec]:
                heapq.heappush(hq, (w+wei,v))
 
V, E = map(int,input().split())
INF = 2147483647
distance = [INF] * (V+1)
K = int(input())
distance[K] = 0
adjList = [[] for _ in range(V+1)]
 
for _ in range(E):
    a,b,w = map(int,input().split())
    adjList[a].append((b,w))
 
hq = []
 
for v, w in adjList[K]:
    heapq.heappush(hq, (w,v))
 
BFS(hq)
 
for d in distance[1:]:
    if d ==INF:
        print("INF")
        continue
    print(d)

---