[Python] 백준 1753번. 최단경로

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

1753번: 최단경로

문제설명:

정점의 개수 V와 간선의 개수 E가 주어지고

시작 정점의 번호 K가 주어졌을 때 i번째 줄에서 i번 정점으로의 최단 경로의 경로값을 출력한다.

 

이 문제는 시작점이 K가 주어졌기 때문에 다익스트라 알고리즘으로 풀어본다.

 

• graph을 생성하자 여기에는 3개의 숫자 a,b,c 가 받아질때 graph[a].append((점, 간선))으로 받으려고 한다.

INF = int(1e9)

v, e = map(int, input().split())
start = int(input())
graph = [[] for _ in range(v+1)]

 

 

• dist는 최단경로의 값을 넣어 줄 리스트이다.
• q에 넣고빼고를 반복하며 기존의 경로와 새로운 경로를 비교해 작은 값을 dist에 업로드 해준다.

n = len(graph)
dist = [INF] * n

q = [(0,start)]
dist[start] = 0

while q:
    acc, cur = heapq.heappop(q)
    
    for adj, d in graph[cur]:
        cost = acc+d
        if cost < dist[adj]:
            dist[adj] = cost
            heapq.heappush(q, (cost,adj))

 

 

• 시간초과가 났다.
• 조건없이 무조건 while , for문이 돌아서 그런가 생각해 조건문을 추가해보기로 한다.

 

• 조건문을 추가해 만약 기존의 값보다 경로의 길이가 크면 for문을 돌지 않고 다음 큐를 꺼내도록 하려했다.
• 위의 두번째 시간초과가 났다.

while q:
    acc, cur = heapq.heappop(q)
    
    if dist[cur] < acc:
            continue
    
    for adj, d in graph[cur]:
        cost = acc+d
        if cost < dist[adj]:
            dist[adj] = cost
            heapq.heappush(q, (cost,adj))

 

 

 

• input도 sys 모듈에 있는 걸 사용했다.

input = sys.stdin.readline
v, e = map(int, input().split())
start = int(input())
dist = [INF] * (v+1)

def Dijkstra(graph):
    q = [(0,start)]
    dist[start] = 0

    while q:
        acc, cur = heapq.heappop(q)

        if dist[cur] < acc:
            continue

        for adj, d in graph[cur]:
            cost = acc+d
            if cost < dist[adj]:
                dist[adj] = cost
                heapq.heappush(q, (cost,adj))

    return dist