파이썬 알고리즘 272번 | [백준 1916 번] 최소비용 구하기 - 그래프 / 다익스트라 알고리즘

272. 그래프 최소비용 구하기

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

• 그래프, 다익스트라

2) 코딩 설명

<내 풀이>

from collections import deque
import heapq
import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

my = [ [] for _ in range(n+1) ]

for i in range(m) : 
    s,e,p = map(int, sys.stdin.readline().split())
    my[s].append((e,p)) # s에서 갈 수 있는 후보들 저장 

start, end = map(int, sys.stdin.readline().split())

q=deque()
q.append((start, 0))
min_price = [10000000000000000001 for _ in range(n+1)]
min_price[start] = 0 # 동일하면 비용 0

while q :
    ts, pri = q.popleft() 
    if min_price[ts] >= pri :
        for next,price in my[ts] :
                if min_price[next]>pri+price:
                    min_price[next] = pri+price
                    q.append((next, pri+price))
                
print(min_price[end])

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

1) 틀렸던 풀이 : 시간초과

from collections import deque
import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
mapp = [[0 for _ in range(n+1)] for _ in range(n+1)]

for i in range(m) : 
    s,e,p = map(int, sys.stdin.readline().split())
    if mapp[s][e]>0 :
        if p<mapp[s][e] :
            mapp[s][e] = p
    else : mapp[s][e] = p

start, end = map(int, sys.stdin.readline().split())

q = deque()
q.append((start,0,[]))

min_price = 9999999999999

while q :
    
    ts, pri, visited = q.popleft() 
    visited.append(ts)

    if ts==end : 
        # print("\n", ts, pri, visited, " hi \n")
        if pri<min_price:
            min_price=pri

    for i in range(1,n+1) :
        if i not in visited and mapp[ts][i]>0:
            q.append((i,pri+mapp[ts][i],visited))

print(min_price)

2) 보니깐 길이로 0 이 들어올 수도 있었다.. my 라는 배열을 만들어서 간선 만들어주는 리스트 추가

from collections import deque
import heapq
import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
mapp = [[0 for _ in range(n+1)] for _ in range(n+1)]
my = [ [] for _ in range(n+1) ]
for i in range(m) : 
    s,e,p = map(int, sys.stdin.readline().split())
    if mapp[s][e]>0 :
        if p<mapp[s][e] :
            mapp[s][e] = p
    else : mapp[s][e] = p
    my[s].append(e)

start, end = map(int, sys.stdin.readline().split())

q = []
visited = []
#q.append((start,0,[]))
heapq.heappush(q, (start, 0, visited))

min_price = [999999 for _ in range(n+1)]

while q :
    ts, pri, visited = heapq.heappop(q) #q.popleft() 
    visited.append(ts)
    #print(visited, ts, pri, min_price," \n")
    if min_price[ts] >= pri :
        min_price[ts]=pri
        for i in my[ts] :
            if i not in visited :
                #print(min_price[i] , " ", pri+mapp[ts][i], "\n")
                if min_price[i]>pri+mapp[ts][i]:
                    min_price[i] = pri+mapp[ts][i]
                    heapq.heappush(q, (i, pri+mapp[ts][i], visited))

print(min_price[end])

=> 그러나 13%에서 틀림, visited 조건 빼주기

3) 53%에서 틀림

from collections import deque
import heapq
import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
mapp = [[0 for _ in range(n+1)] for _ in range(n+1)]
my = [ [] for _ in range(n+1) ]
for i in range(m) : 
    s,e,p = map(int, sys.stdin.readline().split())
    if mapp[s][e]>0 :
        if p<mapp[s][e] :
            mapp[s][e] = p
    else : mapp[s][e] = p
    my[s].append(e)

start, end = map(int, sys.stdin.readline().split())

q = []
visited = []
#q.append((start,0,[]))
heapq.heappush(q, (start, 0, visited))

min_price = [999999 for _ in range(n+1)]

while q :
    ts, pri, visited = heapq.heappop(q) #q.popleft() 
    visited.append(ts)
    if min_price[ts] >= pri :
        min_price[ts]=pri
        for i in my[ts] :
                if min_price[i]>pri+mapp[ts][i]:
                    min_price[i] = pri+mapp[ts][i]
                    heapq.heappush(q, (i, pri+mapp[ts][i], visited))

print(min_price[end])

4) ...? ㅋㅋ 계속 100%에서 틀렸다뜨네;; 열받는다 크아악

from collections import deque
import heapq
import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
mapp = [[0 for _ in range(n+1)] for _ in range(n+1)]
my = [ [] for _ in range(n+1) ]
for i in range(m) : 
    s,e,p = map(int, sys.stdin.readline().split())
    if mapp[s][e]>0 :
        # s에서 e 로 가는 p(비용, 거리) 저장
        if p<mapp[s][e] : # 더 작은 값을 비용으로 등록해주기 
            mapp[s][e] = p 
    else : mapp[s][e] = p
    my[s].append(e) # s에서 갈 수 있는 후보들 저장 

start, end = map(int, sys.stdin.readline().split())

q=deque()
q.append((start, 0))

min_price = [10000000000001 for _ in range(n+1)]

while q :
    ts, pri = q.popleft() 
    if min_price[ts] >= pri :
        for i in my[ts] :
            if min_price[i]>pri+mapp[ts][i]:
                min_price[i] = pri+mapp[ts][i] 
                q.append((i, pri+mapp[ts][i]))
    else : 
        continue
print(min_price[end])

5) 여전히 100에서. 미취겠다..

from collections import deque
import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

mapp = [[0 for _ in range(n+1)] for _ in range(n+1)]
my = [ [] for _ in range(n+1) ]

for i in range(m) : 
    s,e,p = map(int, sys.stdin.readline().split())
    if mapp[s][e]>0 :
        # s에서 e 로 가는 p(비용, 거리) 저장
        if p<mapp[s][e] : # 더 작은 값을 비용으로 등록해주기 
            mapp[s][e] = p 
    else : mapp[s][e] = p
    my[s].append(e) # s에서 갈 수 있는 후보들 저장 

start, end = map(int, sys.stdin.readline().split())

q=deque()
q.append((start, 0))

min_price = [10000000000000000001 for _ in range(n+1)]

while q :
    ts, pri = q.popleft() 
    if min_price[ts] < pri :
        continue
    for i in my[ts] :
            if min_price[i]>pri+mapp[ts][i]:
                min_price[i] = pri+mapp[ts][i] 
                q.append((i, pri+mapp[ts][i]))
                
print(min_price[end])

6) deque

from collections import deque
import heapq
import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

my = [ [] for _ in range(n+1) ]

for i in range(m) : 
    s,e,p = map(int, sys.stdin.readline().split())
    my[s].append((e,p)) # s에서 갈 수 있는 후보들 저장 

start, end = map(int, sys.stdin.readline().split())

q=deque()
q.append((start, 0))
min_price = [10000000000000000001 for _ in range(n+1)]
min_price[start] = 0 # 동일하면 비용 0

while q :
    ts, pri = q.popleft() 
    if min_price[ts] >= pri :
        for next,price in my[ts] :
                if min_price[next]>pri+price:
                    min_price[next] = pri+price
                    q.append((next, pri+price))
                
print(min_price[end])

<반성 점>

아무래도 이 부분에서 뭔가 예상치 못한 오류가 있었던 듯,,?
일단 나는 같은 출발, 같은 도착지 가지는 거가 여러개 들어오면 가장 작은애가 저장되도록 해놨는데 흠,,
그냥 내가 갈 수 있는 간선 후보들을 모조리 다 저장해놓고 돌렸더니 되드라
하지만 명확한 원인은 몰라서 좀 아쉬워!!

<배운 점>

https://justkode.kr/algorithm/python-dijkstra
다익스트라 복습 ,,
heapq 로 하는 것이 일반적이구나 으흠

import heapq  # 우선순위 큐 구현을 위함

graph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

def dijkstra(graph, start):
  distances = {node: float('inf') for node in graph}  # start로 부터의 거리 값을 저장하기 위함
  distances[start] = 0  # 시작 값은 0이어야 함
  queue = []
  heapq.heappush(queue, [distances[start], start])  # 시작 노드부터 탐색 시작 하기 위함.

  while queue:  # queue에 남아 있는 노드가 없으면 끝
    current_distance, current_destination = heapq.heappop(queue)  # 탐색 할 노드, 거리를 가져옴.

    if distances[current_destination] < current_distance:  # 기존에 있는 거리보다 길다면, 볼 필요도 없음
      continue
    
    for new_destination, new_distance in graph[current_destination].items():
      distance = current_distance + new_distance  # 해당 노드를 거쳐 갈 때 거리
      if distance < distances[new_destination]:  # 알고 있는 거리 보다 작으면 갱신
        distances[new_destination] = distance
        heapq.heappush(queue, [distance, new_destination])  # 다음 인접 거리를 계산 하기 위해 큐에 삽입
    
  return distances