[백준 1916번] 최소비용 구하기

문제 출처

문제 유형

• 그래프 이론
• 데이크스트라(다익스트라)

풀이

해당 문제는 solved.ac 사이트 기준 골드 5 문제입니다.

난이도가 골드 5임에도 정답률이 32%로 낮은축에 속하는 것 같습니다.
n개의 도시, m개의 버스가 있고 시작 도시에서 출발 도시까지의 시간이 가장 짧은 비용을 찾는 문제입니다.

• 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다

• 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

• M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

전형적인 다익스트라 문제입니다. 다익스트라의 공식을 그대로 사용하면 되는데 제 경우에는 초반에 특정 조건 (여러 개의 버스 가운데 가장 짧은 길) 을 생각못해 조금 해맸습니다.

풀이 코드

import heapq, sys
input = sys.stdin.readline

n = int(input())
m = int(input())

busSet = {}
def dijkstra(busSet, start):
    # 거리를 저장할 배열생성
    distArr = {node: float('inf') for node in range(n + 1)}
    # 자기 자신의 거리 0
    distArr[start] = 0

    queue = []
    heapq.heappush(queue, [distArr[start], start])

    while queue:
        now_distance, now_destination = heapq.heappop(queue)

        # 배열목록에 목적지에 해당하는 버스가 없거나 저장된 거리보다 현재의 거리가 더 클때는 생략
        if now_destination not in busSet or distArr[now_destination] < now_distance:
            continue
        for new_destination, new_distance in busSet[now_destination].items():
            # 여기까지 온 거리 + 현재 버스의 거리들을 더하기
            distance = now_distance + new_distance

            # 기존 거리가 더 크면
            if distance < distArr[new_destination]:
                # 기존 거리 갱신
                distArr[new_destination] = distance
                heapq.heappush(queue, [distance, new_destination])

    return distArr

# dict 만들어주기
for x in range(m):
    s, e, d = map(int, input().split())

    if s in busSet:
        if e in busSet[s]:
            if busSet[s][e] > d:
                busSet[s][e] = d
        else:
            busSet[s][e] = d
    else:
        busSet[s] = {e: d}

start, destination = map(int, input().split())
print(dijkstra(busSet, start)[destination])