새싹프로그래머의 이야기

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

solved.ac의 class 4로 진입했는데 갑자기 난이도가 너무 높아져서 당황했습니다. 진짜 해결 방안이 쉽사리 떠오르지 않더라구요. 

문제 푸는데 시간이 꽤 오래 걸린 문제였습니다...

문제: 도시 ~ 도시의 비용이 주어졌을 때, 출발 도시에서 도착 도시까지의 최소비용을 구하는 문제 입니다.

풀이 방법: heapq를 이용하여 최소 cost 계산.

풀이 설명:

일단 입력 값에 대해 다음과 같이 graph를 구성하였습니다.

for _ in range(m):
    node1, node2, value = map(int,sys.stdin.readline().rstrip().split())
    graph[node1].append((value,node2))

이때, 값을 (value,node) 순으로 구성한 이유는 heapq를 비용 기준으로 활용할 계획이기 때문입니다.

graph와 heapq를 통해 시작점으로 부터 갈 수 있는 노드의 비용들을 탐색하고, 이 과정에서 도착 노드에 대해 나오는 결과 값들 중 최소 값만 저장되도록 다음과 같이 코드를 작성하였습니다 . 

heapq.heappush(heap, [0, start])# 초기 값을 시작점으로 setting
dist[start] = 0# 시작점 cost = 0

while heap:
    cost, node = heapq.heappop(heap)

    if cost > dist[node]:
        continue

    for i in graph[node]:# 시작점으로부터 도달할 수 있는 노드 탐색
        nextCost, nextNode = i
        distance = nextCost + cost

        if dist[nextNode] > distance:
            dist[nextNode] = distance# 기존 입력된 거리와 새로 계산된 거리의 최소 값 저장
            heapq.heappush(heap, [distance, nextNode])
        else:
            continue

풀이 코드:

import sys
import heapq

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

graph = [[]*(n+1) for _ in range(n+1)]
dist = [1E9]*(n+1)
heap = []

for _ in range(m):
    node1, node2, value = map(int,sys.stdin.readline().rstrip().split())
    graph[node1].append((value,node2))

start, destination = map(int,sys.stdin.readline().rstrip().split())

heapq.heappush(heap, [0, start])# 초기 값을 시작점으로 setting
dist[start] = 0# 시작점 cost = 0

while heap:
    cost, node = heapq.heappop(heap)

    if cost > dist[node]:
        continue

    for i in graph[node]:# 시작점으로부터 도달할 수 있는 노드 탐색
        nextCost, nextNode = i
        distance = nextCost + cost

        if dist[nextNode] > distance:
            dist[nextNode] = distance# 기존 입력된 거리와 새로 계산된 거리의 최소 값 저장
            heapq.heappush(heap, [distance, nextNode])
        else:
            continue
print(dist[destination])