[백준 | 파이썬3] 1753. 최단경로- 다익스트라/ 런타임에러 input() vs stdin.readline

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

1753번: 최단경로

> 다익스트라 알고리즘 활용

 

해당 문제는 알고리즘 구현보단 데이터를 입력하는 부분에서 애를 먹었다. 처음에는 모든 데이터를 input()으로 받았더니 계속 런타임 에러가 났다.

 

이럴때는 sys.stdin.readline을 사용해줘야한다. 

참고한 글에 따르면 input()과 stdin는 내가 어떤 input을 입력받느냐에 따라 소요시간이 달라질 수 있다고 한다.

 

 

그 이유는 첫번째로,

input()의 경우 데이터를 입력받을때 prompt parameter가 실행된다. 이러한 과정이 과부하를 일으킬 수 있다. 그러나 input함수가 각각의 readline 호출함수 전에 값들을 print하는 코드보다는 실행시간이 빠를 수 있다고는 한다. 

 

두번째로,

input함수는 input으로 들어온 값의 끝부분의 '\n' 개행문자를 삭제한 후 입력된다. 하지만 stdin의 경우 이러한 과정이 생략된다. 따라서 stdin이 일반적으로 더 빠를 수 있다. 

 

 

즉 input과 stdin을 쓰냐마냐는 내가 원하는 입력값의 형태가 어떻게 될지에 따라 다르지만 일반적으로 많은 양의 데이터를 입력받을땐 input보다는 stdin을 사용하는 것이 훨씬 빠르다고 한다. 

 

---

따라서 해당 문제에 대한 코드는 다음과 같이 작성하여 input함수가 stdin.readline을 통해 값들을 읽어오도록 설정하였다. 

 

import heapq
import sys

input = sys.stdin.readline
V,E = map(int,input().split())
k= int(input())

INF= int(1e9)
distance= [INF]*(V+1)
graph=[[] for i in range(V+1)]

for _ in range(E):
    u, v, w= map(int, input().split())
    graph[u].append((v,w))
    
    

def dijkstra(start):
    q=[]
    heapq.heappush(q, (0, start))
    distance[start]=0
    
    while q:
        dist, now= heapq.heappop(q)
  
        if distance[now] < dist:
            continue

        for ver,wei in graph[now]:
            cost= dist + wei
            
            
            if cost < distance[ver]:
                distance[ver]= cost
                heapq.heappush(q,(cost, ver))

    
dijkstra(k)

for i in range(1,V+1):
    print("INF" if distance[i] == INF else distance[i])