글 읽기 - heapq heappush 코드 차이점이 뭔지 아시는분 계신가요?

wofhdjxor 3년 전 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import sys
import heapq
 
V, E = list(map(int, sys.stdin.readline().split()))
k = int(sys.stdin.readline().split()[0])
 
minNum = float('inf')
route = [[] for _ in range(V + 1)]
dji = [minNum for _ in range(V + 1)]
 
def dijAlg(root) :
    heap = []
    heapq.heappush(heap, [root, 0])
    dji[root] = 0
 
    while heap :
        point, dis = heapq.heappop(heap)
        if dji[point] < dis :
            continue
 
        for i in route[point]:
            cost = dis + i[1]
 
            if cost < dji[i[0]]:
                dji[i[0]] = cost
                heapq.heappush(heap, [i[0], cost])        
 
for i in range(E) :
    u, v, w = list(map(int, sys.stdin.readline().split()))
    route[u].append([v, w])
 
dijAlg(k)
for i in range(1, V + 1) :
    if dji[i] == minNum :
        print('INF')
    else :
        print(dji[i])
Colored by Color Scripter
cs

위에 코드와 밑에 코드는 heappush의 인자랑 point, dis = heapq.heappop(heap) 여기서 변수 받는 위치만 바꿨는데 왜 하나는 시간초과가 나는건가요?

import sys
import heapq

V, E = list(map(int, sys.stdin.readline().split()))
k = int(sys.stdin.readline().split()[0])

minNum = float('inf')
route = [[] for _ in range(V + 1)]
dji = [minNum for _ in range(V + 1)]

def dijAlg(root) :
    heap = []
    heapq.heappush(heap, [0, root])
    dji[root] = 0

    while heap :
        dis, point = heapq.heappop(heap)
        if dji[point] < dis :
            continue

        for i in route[point]:
            cost = dis + i[1]

            if cost < dji[i[0]]:
                dji[i[0]] = cost
                heapq.heappush(heap, [cost, i[0]])        

for i in range(E) :
    u, v, w = list(map(int, sys.stdin.readline().split()))
    route[u].append([v, w])

print(route)
dijAlg(k)
for i in range(1, V + 1) :
    if dji[i] == minNum :
        print('INF')
    else :
        print(dji[i])

dps2 3년 전 1

다익스트라 알고리즘을 잘 생각해보시면 구현 방법이 가까운 곳 부터 visit해서 거리를 확정시켜나갑니다.

heapq는 프라이어리티 큐여서 작은 원소를(min heap에서는) pop 시킵니다.

이때 리스트,튜플 같은 자료형에서 (a,b,c) (d,e,f) 두 원소 비교(리스트라면 () 대신 [])는 사전순입니다.

무슨 말인가 하면 앞에서부터 하나씩 비교해서 먼저 큰 원소가 나오는 쪽이 크다는 것입니다.

예를 들어 (0,5,7) (0,10,-10) 이면 제일 앞에 있는 수는 둘 다 0으로 같으므로 다음 수를 보게 됩니다.

다음 수는 5와 10이고 5<10 이므로 더이상 뒤에 있는 수를 보지 않고 (0,5,7) < (0,10,-10) 이라고 판단하게 됩니다.

지금 코스트와 노드번호를 바꾸는건 크게 달라보이지 않을 수 있지만

하나는 거리 순대로 pop되게 하여 다익스트라 알고리즘이고, 다른 하나는 다익스트라가 아닌 이상한 알고리즘이 됩니다.

따라서 하나는 시간초과가 뜨지 않은것이고 다른 하나는 시간초과가 난 것입니다.

wofhdjxor 3년 전 1

heapq.heappush() 위치만 바꿨을 뿐인데 그런식으로 변하는 건 전혀 모르고 있었네요......

답변 정말 감사드립니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

heapq heappush 코드 차이점이 뭔지 아시는분 계신가요?

wofhdjxor 3년 전 0

dps2 3년 전 1

wofhdjxor 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말