백준 1916번 최소 비용 구하기 | python | 다익스트라 알고리즘

문제

링크

풀이

다익스트라 알고리즘을 그대로 구현하여 풀이하는 문제이다. 따라서 다익스트라 알고리즘 개념과 구현방식을 알고있다면 바로 정답을 맞출 수 있다.

따라서 풀이 과정은 간략한 주석으로 대체하고, 관련 포스팅 링크를 첨부하겠다.

코드는 아래와 같다

# 다익스트라 알고리즘
import heapq
import sys

input = sys.stdin.readline

INF = int(1e9)  # 10억
n = int(input().strip())
m = int(input().strip())

graph = [[] for i in range(n + 1)]
distance = [INF] * (n + 1)

for i in range(1, m + 1):
    a, b, c = map(int, input().strip().split())
    # a번 노드에서 b로 가는 비용이 c라는 의미
    graph[a].append((b, c))

# 모든 간선 정보 입력
start, end = map(int, input().strip().split())


def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))  # (비용(거리)), 노드 번호)
    distance[start] = 0
    # 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택
    while q:
        curCost, curNode = heapq.heappop(q)
        # distance[curNode]보다 curCost가 크다면 방문한 노드임
        if distance[curNode] < curCost:
            # 다익스트라 알고리즘은 특정 노드(start)를 기준으로 모든 노드에 대한 최단 거리를 구하지만,
            # 문제에서는 모든 노드가 아닌 end 인덱스를 가진 노드에 대한 최단 거리만 요하므로 해당 값을 구하면 바로 break 처리
            if curNode == end:
                break
            else:
                continue
        for i in graph[curNode]:
            cost = curCost + i[1]
            if distance[i[0]] > cost:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))


dijkstra(start)

print(distance[end])

🦾 깨달은 점

1. 다익스트라 알고리즘과 플로이드 워셜 알고리즘에 대해 진득하게 배울 수 있었다. 이코테 최단 경로 알고리즘 강의 2배속으로 두 번 보니까 이해되었다.
2. input()과 sys.stdin.readline의 차이점에 대해 알게 됨
   • input()
     • 인자로 주어진 문자를 화면에 출력하고 사용자의 입력을 기다린다.
     • 개행 문자는 입력의 종료로 간주한다.
     • 무엇을 입력하든 문자열로 변환하고 줄 바꿈을 제거한 뒤 값을 반환한다.
     • 사용자가 키를 누르면 그에 대응하는 데이터가 하나씩 버퍼에 들어간다.
     • 결론 : 느리다
   • sys.stdin.readline()
     • input()과 달리 문자를 화면에 출력하는 기능이 없다.
     • 한 번에 읽을 수 있는 글자 수 크기에 대한 매개변수가 제공된다.
     • 한 번에 읽어와 버퍼에 저장한다.
     • 결론 : 빠르다
3. 코딩테스트에서 python으로 문제를 풀 때엔 sys.stdin.readline을 습관처럼 사용해야겠다.