백준 / 최소비용 구하기 / 1916번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 최소비용 구하기 / 1916번 (골드 5단계)

문제 사이트: https://www.acmicpc.net/problem/1916

 

문제 설명

 

---

 

나의 풀이

 

1번 코드

from collections import deque

INF = 1e9

# 다익스트라 알고리즘
def usg(graph, start, target):
    q = deque()
    q.append((start, 0))
    d = [INF] * (len(graph) + 1)
    d[start] = 0

    while q:
        current, distance = q.popleft()

        if (d[current] < distance):
            continue

        for i in range(len(graph[current])):
            next, weight = graph[current][i]
            nextDistance = distance + weight
            if (nextDistance < d[next]):
                d[next] = nextDistance
                q.append((next, nextDistance))

    return d[target]

N = int(input())
M = int(input())

graph = {i : [] for i in range(1, N + 1)}  # 그래프

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

st, ta = map(int, input().split())
print(usg(graph, st, ta))

 

문제의 조건은 양방향이 아닌 단방향만 고려했을 경우를 생각하고 풀어야하지만 양방향을 고려해서 풀어서 틀렸다.

 

2번 코드

from collections import deque

INF = 1e9

# 다익스트라 알고리즘
def usg(graph, start, target):
    q = deque()
    q.append((start, 0))
    d = [INF] * (len(graph) + 1)
    d[start] = 0

    while q:
        current, distance = q.popleft()
        distance = -distance

        if (d[current] < distance):
            continue

        for i in range(len(graph[current])):
            next, weight = graph[current][i]
            nextDistance = distance + weight
            if (nextDistance < d[next]):
                d[next] = nextDistance
                q.append((next, -nextDistance))

    return d[target]

N = int(input())
M = int(input())

graph = {i : [] for i in range(1, N + 1)}  # 그래프

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

st, ta = map(int, input().split())
print(usg(graph, st, ta))

 

이 풀이는 단방향인데 시간초과가 발생했다. 아마도 deque()를 사용하기도 했고 굳이 음수로 변환할 필요가 없지만 변환을 해서 시간이 더 오래 걸린 것 같다. 하지만 이 풀이는 PyPy3에서 제출하면 정답이 되긴한다.

 

import heapq
import sys
input = sys.stdin.readline

INF = 1e9

def dijkstra(graph, start, target):
    q = []
    heapq.heappush(q, (0, start))
    distances = [INF] * (N + 1)
    distances[start] = 0

    while q:
        current_distance, current_node = heapq.heappop(q)

        if distances[current_node] < current_distance:
            continue

        for next_node, weight in graph[current_node]:
            distance = current_distance + weight
            if distance < distances[next_node]:
                distances[next_node] = distance
                heapq.heappush(q, (distance, next_node))

    return distances[target]

# 입력 처리
N = int(input())
M = int(input())

graph = {i: [] for i in range(1, N + 1)}

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

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

# 다익스트라 알고리즘을 사용하여 최소 비용 계산
print(dijkstra(graph, start, target))

 

위 코드들의 최적화를 한 코드다. 힙을 사용하여 최적의 비용을 찾는 방식을 선택했다.

이 코드는 Python 3에서 정답이 된다.

---

※ 알아야 할 것

 

https://littlefoxdiary.tistory.com/3

[Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기