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

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

1916번: 최소비용 구하기

문제 한줄 이해

-N개의 도시가 주어지고 M개의 버스들이 출발 도시에서 도착 도시까지 가는 비용을 가지고 있을때

원하는 시작 도시에서 도착 도시까지의 최소 비용 구하기

 

생각난 풀이

1번째 방법: 오랜만에 다익스트라 문제를 만났다. 다익스트라가 무엇이냐 하면 간단히 얘기하면 특정 노드에서 다른 노드로 갈 수 있는 최소 가중치를 가지도록 하는것이다. 이때 다익스트라를 적용하기 위해서는 우선순위큐, 어떤 그래프를 쓸지 결정해야한다. 나는 먼저 인접행렬로 표현한 그래프가 떠올랐다.

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

#버스의 비용이 0<=비용<=100000이므로 이 범위에 없다는 것은 해당 버스가 없다!
bus = [[1e9 for i in range(n+1)] for i in range(n+1)]

#각 버스의 정보를 담을때 중복돼서 들어올수도 있으므로 그중 작은 값은 선택해서 저장
for i in range(m):
    a,b,v = map(int,sys.stdin.readline().split())
    if bus[a][b] > v:
        bus[a][b] = v
start, end = map(int,sys.stdin.readline().split())

#거리 정보
dis = [1e9] * (n+1)

def dik(start):
    hq = []
    #출발도시랑 도착도시가 같은 경우는 없다.
    heapq.heappush(hq,(0,start))
    dis[start] = 0
    while hq:
        dist, nown = heapq.heappop(hq)
        
        #현재 꺼낸 거리값이 이미 저장돼 있는 값보다 크다면 비교할 필요 X
        if dis[nown] < dist:
            continue    
        
        for i in range(1,n+1):
            if bus[nown][i] != 1e9:
                nowdist = bus[nown][i] + dist
                if nowdist < dis[i]:
                    dis[i]  = nowdist
                    heapq.heappush(hq,(nowdist,i))
dik(start)
print(dis[end])

제출을 하고 틀렸다. 분명 내가 생각한 흐름에 의해 코드를 짜내고 문제가 없다고 생각했는데 왜??? 계속 고민한 결과 버스의 정보를 저장할때 a도시 b도시의 값이 여러번 들어 올수도 있겟다라는 생각해 조건을 걸었더니 해결했다! (하지만 문제에 주어진 정보들이 손실? 된다...)

 

2번째 방법: 연결리스트 활용

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

bus = [[] for i in range(n+1)]

for i in range(m):
    a,b,v = map(int,sys.stdin.readline().split())
    bus[a].append((v,b))
start, end = map(int,sys.stdin.readline().split())
dis = [1e9] * (n+1)

def dik(start):
    hq = []
    heapq.heappush(hq,(0,start))
    dis[start] = 0
    while hq:
        dist, nown = heapq.heappop(hq)
        
        if dis[nown] < dist:
            continue    
        
        for i in bus[nown]:
            nowdist = i[0] + dist
            if nowdist < dis[i[1]]:
                dis[i[1]]  = nowdist
                heapq.heappush(hq,(nowdist,i[1]))
                
dik(start)
print(dis[end])

연결리스트를 활용하면 문제에서 들어오는 정보들을 그래프에 다 담아 둘수 있다. 또한 연결리스트에서 다 담아도 문제가 되지 않는 이유는 우선순위 큐에 있다. 어차피 우리가 계산해 나가는 거리 정보에는 이미 계속 작은값으로 갱신이 돼있기 때문에 a도시 b도시의 정보들이 여러번 들어가더라도 if dis[now] < dist 조건절에 걸리기 때문에 문제가 되지 않는다!