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

문제링크:1916번: 최소비용 구하기 (acmicpc.net)

1916번: 최소비용 구하기

처음 다익스트라 알고리즘을 모르고 dfs로 시작 노드부터 가능한 노드까지 모두 탐색하여 최소값을 찾는 방식으로 했지만 당연하게 시간 초과가 났다. 다익스트라 알고리즘에 대해 인터넷에 찾아 본 후 다익스트라 알고리즘을 사용하여 문제를 해결하였다.

import sys
import heapq

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

graph=[[] for _ in range(N+1)]

for i in range(M):
    a,b,c=map(int,sys.stdin.readline().rstrip().split())
    graph[a].append([b,c])

startpoint,endpoint=map(int,sys.stdin.readline().rstrip().split())

def dijkstra(start):
    d=[999999999 for _ in range(N+1)]
    d[start]=0
    que=[]
    heapq.heappush(que,(d[start],start))
    while que:
        dis,node=heapq.heappop(que)
        if d[node]<dis: #이미 노드에 대한 최단거리 존재시 과정 패스 
            continue
        for i in graph[node]: #node의 노드에서 거리비용 탐색
            gnode=i[0] #그래프에서 탐색당하는 노드
            gdis=i[1] #그래프에서 탐색당하는 노드의 거리비용
            updatedis=d[node]+gdis
            if updatedis<d[gnode]:
                d[gnode]=updatedis
                heapq.heappush(que,(d[gnode],gnode))
    return d

print(dijkstra(startpoint)[endpoint])

다익스트라 알고리즘은 노드간 간선의 비용이 모두 양수일때 노드간 이동 비용의 최소값을 구하는 문제에서 주로 사용된다. 보통 최단 거리 판별할때 사용되는 알고리즘이라고 한다. 다익스트라 알고리즘의 과정과 코드에서의 과정은 다음곽 같다.

 

 

1. 시작점을 정한다. 위의 코드에선 dijkstra 함수의 start를 시작점으로 입력받는다.

 

2. 노드 개수만큼의 거리 리스트를 만든다. 거리 리스트는 초기에는 시작 노드 외의 노드는 최단 거리를 모르므로 무한대로 판별될 수 있을정도로 큰 수를 대입한다. 코드에서는 N+1개의 999999999를 가진 리스트 d를 만들고 d[start]=0 을 했다.

 

3.출발 노드부터 각 노드의 최소 비용을 탐색한다. 앞으로 출발 노드 외의 다른 노드도 탐색할 것인데 다른 노드를 탐색하는 순서는 최단 거리가 짧은 순으로 하기 때문에 heap을 사용했고, 노드가 아닌 (d[노드],노드) 순서로 넣어 힙이 최단거리가 가장 작은 노드부터 탐색할 수 있도록 했다.

 

4.다음 순서의 노드로부터의 최소 비용을 탐색하는 과정을 반복한다. while que: 아래에 if d[node]<dis: 를 선언해주는 이유는 이미 노드에 대한 최단거리를 탐색 했는데 heap 자료구조에 그 노드가 남아있는 경우가 있기 때문이다. 처음 문제풀때 이걸 선언하지 안하서 시간 초과가 발생했다. 아래에 예시 설명을 들겠다.

 

그래프가 만약

노드 번호 = [[도착노드1, 간선비용1], [도착노드2,간선비용2]] 형식일때,

node 1 =[[2,1], [3,4]]

node 2 =[[3,1]]

node 3 =[[1,1]]

인 경우, 시작점을 node1 로 잡는 경우:

 

1. que에 (0,1)이 들어가고 반환된다. 노드 1의 (1,2), (4,3)가 que에 들어가고 d[2]=1, d[3]=3으로 갱신된다. que에 들어갈땐 (간선비용, 도착노드) 형식으로 들어가는 것에 유의한다

 

2. que에서 가장 작은 (1,2)가 반환된다. 이 과정에서 노드 2의 간선이 (1,3)으로 que에 들어가고 d[3]=d[2]+1 ( = 2) 으로 갱신된다. 현재 d는 [99999999, 0, 1, 2] 인 상태이다.

 

3. que에서 (4,3) 보다 작은 (1,3)이 반환되고 노드3의 간선이 있지만 d[0] (0) < d[3]+1 (3) 이므로 갱신되지 못한다.

 

4. que에서 남은 (4,3)이 반한되지만 이미 d[3]의 값이 1으로 4보다 작기 떄문에 패스한다. 만약 패스하지 않고 탐색한다면 밑의 for 문장에서 최단거리가 될 수 없는 노드 3의 간선들을 쓸데없이 탐색하게 된다.