파이썬 백준 1916번 : 최소비용 구하기

문제

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

 

 

풀이

다익스트라로 해결했다.

인접행렬로 그래프를 만들었다. 힙 자료구조를 사용해서 힙이 빌때까지 최단 경로 갱신을 반복한다. 

heap 정렬을 위해 (거리,노드번호)의 순으로 넣어줬다. 

import heapq
import sys

def dijkstra(start,end):
    dist = [1e9] * (N + 1)
    visited = set()  # vistied 확인 효율화
    heap = []  # 빈 리스트 하나 생성해서 최소힙 자료구조로 활용
    heapq.heappush(heap, (0, start))  # (거리, 노드번호)

    while heap: 
        distance, node = heapq.heappop(heap)  # 거리와 노드번호를 뽑고 (뽑힌 순간 최소 거리로 뽑혔을 것)
        if node not in visited:  # visited 없는 경우에 한해서 + visited 되지 않은 경우는 바로 다음 힙팝이 실행된다
            dist[node] = distance  # 최소힙에서 뽑았으니까 바로 그녀석의 distance가 최소 이동 거리
            visited.add(node)  # visited에 넣는다

            for destination in range(N + 1):  # 현재의 node에서 갈 수 있는 destination을 모두 체크할건데,
                # 아직 방문하지 않았어야 함과 동시에
                # 목적지까지의 기존 이동거리라고 생각했던 것 > 내 위치까지의 이동거리 + 내 위치로부터 목적지까지의 이동거리를 만족하면
                if destination not in visited and dist[destination] > adj[node][destination] + dist[node]:
                    heapq.heappush(heap, (adj[node][destination] + dist[node], destination))  # 최소힙에 넣는다.

    return dist[end]


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

adj = [[1e9] * (N + 1) for _ in range(N + 1)]  # inf 개념으로 큰 수 넣어줌

for i in range(M):  # 인접행렬 만들기
    st, ed, w = map(int, sys.stdin.readline().split())
    adj[st][ed] = min(w,adj[st][ed])  # 노드들간의 가중치 자체를 인접 행렬에 넣어서 구조화

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

 

 

😎덧)

start, end가 같은 것이 입력될 수 있음에 주의하자!

# 0이 출력되어야함
2
2
1 2 0
1 2 10
1 2