[백준 1916 최소비용 구하기 문제] PYTHON

 

이번 문제는 최소비용 구하기 문제로 방향이 있는 edge들의 최소 비용을 구하면 된다.

우선은 평소와 같이 DFS를 사용하여 구현을 해보려했다. 

아래와 같이 풀었지만 메모리 에러가 발생하여 구글링을 통해

다익스트라 알고리즘을 사용하기로 헀다.

 

def DFS(start, end, cost):
    global answer
    if start == end:
        if cost < answer:
            answer = cost
    for i in range(1, M+1):
        if Mgraph[start][i] != 0:
            cost += Mgraph[start][i]
            if answer <= cost:
                pass
            DFS(i, end, cost)
            cost -= Mgraph[start][i]
            
answer = 100000000
N = int(input())
M = int(input())
Mgraph = [[0 for _ in range(M+1)] for _ in range(M+1)]

for _ in range(M):
    a, b, c = map(int, input().split())
    Mgraph[a][b] = c
start, end = map(int, input().split())
DFS(start, end, 0)
print(answer)

 

다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있다.

또한 각각의 최단 경로를 구하기 위해 전에 구했던 다른 정점까지의 최단 경로를 사용한다.

 

import sys
from heapq import heappush, heappop

def dijkstra(start):
    heap = []
    heappush(heap, (0, start))
    distance[start] = 0
    while heap:
        cost, index = heappop(heap)
        if distance[index] < cost:
            continue
        for a, b in Mgraph[index]:
            if cost+b < distance[a]:
                distance[a] = cost+b
                heappush(heap, (cost+b, a))

input = sys.stdin.readline
N = int(input())
M = int(input())

Mgraph = [[] for _ in range(N+1)]
distance = [sys.maxsize]*(N+1)

for _ in range(M):
    a, b, c = map(int, input().split())
    Mgraph[a].append([b, c])
start, end = map(int, input().split())

dijkstra(start)
print(distance[end])