[백준 11779번] 최소비용구하기(파이썬)

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

11779번: 최소비용 구하기 2

이 문제는 알고리즘로직보다도

시간초과,메모리 초과와의 싸움을 해야하는게

무척이나 힘들었습니다.

이런 경로를 찾는 알고리즘은

다익스트라 알고리즘을 쓰면 쉽게 풀립니다.

https://justkode.kr/algorithm/python-dijkstra

Python으로 다익스트라(dijkstra) 알고리즘 구현하기

 

이것이 다익스트라 알고리즘입니다.

deque로 했던 걸

heap로 받는다 생각하면 

상당히 유사한 알고리즘 패턴이죠.

다만, 이건 이동경로를 heap에 넣고 돌릴 수 있으니

이런 점에서는 deque로 돌릴때보다 좋습니다.

 

그 다음은 경로를 추적하는 것.

저는 heap에 경로 문자열을 받는 방식을 썼었다가

메모리를 잡아먹는거 같아서

chase라는 리스트를 만들어서

역추적하는 식으로 바꿨습니다.

예를들어, 1->2 이런 식으로 이동했다면

chase[2]=1

이렇게 입력하여

'2이전에 1에서 왔다'

이렇게 알수 있게 만들었죠.

#백준 11779번 최소비용 구하기2
from heapq import heappop,heappush
N=int(input())
M=int(input())
city=[[]for _ in range(N+1)]
for _ in range(M):
    a,b,c=map(int,input().split())
    city[a].append([b,c])

start,end=map(int,input().split())

heap=[]
heappush(heap,[0,start])

way=[1e9]*(N+1)
way[start]=0
chase=[1e9]*(N+1)
chase[start]=-1
while heap:

    cnt,now=heappop(heap)
    if way[now]<cnt:
        continue

    for next_go,next_cnt in city[now]:

        if next_cnt+cnt<=way[next_go]:
            way[next_go]=next_cnt+cnt
            heappush(heap,[next_cnt+cnt,next_go])
            chase[next_go]=now

a_list=[end]

chasing=end
while not chasing==start:
    chasing=chase[chasing]
    a_list.append(chasing)




print(way[end])
print(len(a_list))
a_list.reverse()
print(" ".join(map(str,a_list)))

이거 메모리 초과가 난 코드.

#백준 11779번 최소비용 구하기2
from heapq import heappop,heappush
N=int(input())
M=int(input())
city=[[]for _ in range(N+1)]
for _ in range(M):
    a,b,c=map(int,input().split())
    city[a].append([b,c])

start,end=map(int,input().split())

heap=[]
heappush(heap,(0,start))

INF=987654321
way=[INF]*(N+1)
way[start]=0
chase=[i for i in range(0,N+1)]

while heap:

    cnt,now=heappop(heap)
    if way[now]<cnt:
        continue

    for next_go,next_cnt in city[now]:

        if next_cnt+cnt>=way[next_go]:
            continue
        way[next_go]=next_cnt+cnt
        heappush(heap,(next_cnt+cnt,next_go))
        chase[next_go]=now

a_list=[end]

chasing=end
while not chasing==start:
    chasing=chase[chasing]
    a_list.append(chasing)

print(way[end])
print(len(a_list))
a_list.reverse()
print(" ".join(map(str,a_list)))

 

아래가 통과코드입니다.

차이라고는

 

1. heap을 넣어줄 때 []가 아닌 ()사용

 

2. 최소경로를 판단할 때

(way[next_go] vs next_cnt+cnt)

위는 조건이 맞으면 계산

아래는 조건이 맞으면 넘기기

이렇게 구현한 것.

 

흠...대체 이게 어떻게 메모리차이를 유발한지는 모르겠지만...

여튼 메모리상 문제가 있나보네요...허허