파이썬 알고리즘 297번 | [백준 11779번] 최소비용 구하기 2 - 다익스트라/플로이드

297. 최소비용 구하기 2

1) 어떤 전략(알고리즘)으로 해결?

• 처음에 플로이드 워셜, 그러나 시간초과
• 다익스트라

2) 코딩 설명

• 다익스트라에선 next-node가 갱신된다는 것은 now-node를 거쳐 next-node에 온다는 것입니다.
• 따라서 next-node가 갱신될 때마다 next-node 이전에는 now-node가 온다는 것이 확정되는 것이므로 이 now-node, 즉 자신의 이전값을 기억해둡니다.
• 이후 도착지 노드부터 출발지 노드의 이전 값들을 배열에 보관해주면 도착지(마지막)노드 -> ... -> 출발지 노드 까지의 경로가 나타나게 됩니다.

<내 풀이>

from collections import defaultdict
import heapq
import sys

n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())
hq = []
shortest = [1e9 for _ in range(n+1)]
road = [-1 for _ in range(n+1)]
record = defaultdict(list)
answer = []

for i in range(m) : 
    start_city,end_city,cost = map(int,sys.stdin.readline().rstrip().split())
    record[start_city].append((end_city,cost))

target_start, target_end = map(int,sys.stdin.readline().rstrip().split())

hq.append((0, target_start))

while hq :
    now_cost,  now_city = heapq.heappop(hq)
    if shortest[now_city] < now_cost : 
        continue
    else : 
        for next_city, next_cost in record[now_city] :
            if shortest[next_city]  > now_cost+next_cost:
                shortest[next_city] = now_cost+next_cost
                road[next_city] = now_city 
                # 나 이전의 도시를 기억(내 도시 오기 전 거친 직전 도시)
                heapq.heappush(hq,( now_cost+next_cost , next_city))

print(shortest[target_end])

n = target_end
while n!=target_start :
    answer.append(n)
    n = road[n]

answer.append(target_start)
print(len(answer))
answer.reverse() 
# target end -> ... -> target_start 순이라서 reverse() 필요
print(*answer)

< 내 틀렸던 풀이, 문제점>

• 정답은 맞지만 시간초과 !
• 그럼 다익스트라로 접근해 보아야겠습니다

import sys

n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())
dp = [ list(1e9 for _ in range(n+1)) for _ in range(n+1) ]
klis = [ list(0 for _ in range(n+1)) for _ in range(n+1) ]

for i in range(m) : 
    a,b,c = map(int,sys.stdin.readline().rstrip().split())
    if(dp[a][b]>c) : 
        dp[a][b] = c

ts, te = map(int,sys.stdin.readline().rstrip().split())

for kk in range(1,n+1) : 
    for i in range(1,n+1) : 
        for j in range(1,n+1) : 
            if dp[i][j] > dp[i][kk] + dp[kk][j] : 
                dp[i][j] = dp[i][kk] + dp[kk][j]
                klis[i][j] = kk
                
def find(a,b) : 
    if klis[a][b] == 0 :
        return []
    else : 
        k = klis[a][b]
        return find(a,k) + [k] + find(k,b)

print(dp[ts][te])

lis = find(ts,te)
print(2+len(lis))

print(ts ,end = " ")
for i in lis : 
    print(i, end=" ")
print(te)

• 다익스트라로 접근했는데 recursion limit & 메모리 초과가 발생..

from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**5)

n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())
hq = []
shortest = [1e9 for _ in range(n+1)]
road = [-1 for _ in range(n+1)]
record = defaultdict(list)
answer = []

for i in range(m) : 
    start_city,end_city,cost = map(int,sys.stdin.readline().rstrip().split())
    record[start_city].append((end_city,cost))

target_start, target_end = map(int,sys.stdin.readline().rstrip().split())

hq.append((target_start,0))

while hq :
    now_city, now_cost = heapq.heappop(hq)
    if shortest[now_city] < now_cost : 
        continue
    else : 
        for next_city, next_cost in record[now_city] :
            if shortest[next_city]  > now_cost+next_cost:
                shortest[next_city] = now_cost+next_cost
                road[next_city] = now_city # 나 이전의 도시 
                heapq.heappush(hq,(next_city, next_cost))

print(shortest[target_end])

def recur(city) : 
    answer.append(city)
    if road[city]!=-1 : 
        recur(road[city])
        
recur(target_end)

print(len(answer))
answer.reverse() # target end -> ... -> target_start 순으로 출력
print(*answer)

• 재귀문을 그냥 문으로 바꿔줘도 메모리초과

from collections import defaultdict
import heapq
import sys

n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())
hq = []
shortest = [1e9*100 for _ in range(n+1)]
road = [-1 for _ in range(n+1)]
record = defaultdict(list)
answer = []

for i in range(m) : 
    start_city,end_city,cost = map(int,sys.stdin.readline().rstrip().split())
    record[start_city].append((end_city,cost))

target_start, target_end = map(int,sys.stdin.readline().rstrip().split())

hq.append((target_start,0))

while hq :
    now_city, now_cost = heapq.heappop(hq)
    if shortest[now_city] < now_cost : 
        continue
    else : 
        for next_city, next_cost in record[now_city] :
            if shortest[next_city]  > now_cost+next_cost:
                shortest[next_city] = now_cost+next_cost
                road[next_city] = now_city 
                # 나 이전의 도시를 기억(내 도시 오기 전 거친 직전 도시)
                heapq.heappush(hq,(next_city, next_cost))

print(shortest[target_end])

n = target_end
while n!=target_start :
    answer.append(n)
    n = road[n]

answer.append(target_start)
print(len(answer))
answer.reverse() # target end -> ... -> target_start 순으로 출력
print(*answer)

메모리 초과가 난 이유 : heap 에 비용을 먼저가 아닌 city 먼저 넣고 있었기 때문입니다.

• 다익스트라에서 heap 을 사용하는 이유는 최소 비용인 애들을 먼저 검사해주려고 입니다.
• 그래서 먼저 계산된 애들은 확정되도록 말이지요
• 만약 파이썬의 heap에 최소 비용부터 넣지 않으면 최소 비용 기준으로 최소 힙이 구성되지 않습니다 ㅠㅠ
• 그렇기 때문에 hq에 계속해서 데이터가 추가되니깐 배열이 길어지고 ,,, 메모리 초과가 일어나게 된 것이지요

7프로에서 틀린 이유 :

• 이제 shortest를 갱신하면 갱신된 노드(next-city)를 heap에 넣어줘야 합니다.
• 이때 heap 에 넣을 때 비용은 next-city의 기존 비용(next-cost) 에다가 현재 city(now-city)를 거쳐가는게 확정된 상황이므로 갱신된 비용은 (next-cost + now-cost) 입니다.
• 따라서 heap에 갱신된 비용을 넣어주어야 합니다. 그런데 저는 next-cost만 넣어주고 있었네요 호호

<반성 점>

• 메모리 초과
  • 원인 ) heap 에 넣을 때 비용이 적은 순으로 넣었어야 함 (비용, city 순으로)
  • 그래야지 최소 힙으로 구성되니깐..
• 7프로 틀림
  • 원인 ) heap 에 넣을 때 다음 city에 대한 갱신된 비용 넣어야 하는데 next_cost로만 넣었었음
  • 따라서 now_cost+next_cost 를 넣어줌
• 이때 heap 에 넣을 때 비용은 next-city의 기존 비용(next-cost) 에다가 현재 city(now-city)를 거쳐가는게 확정된 상황이므로 갱신된 비용은 (next-cost + now-cost) 입니다.
  - 따라서 heap에 갱신된 비용을 넣어주어야 합니다.

<배운 점>

• heap을 쓰는 이유는 최소 힙으로 구성, 다익스트라에서는 당연히 비용을 적은 순으로 검사하는 것이 중요하므로 비용 기준으로 최소 힙