[Python] 백준 1916: 최소비용 구하기 (dijkstra)

문제 링크

1916번: 최소비용 구하기

문제 요약

N개의 도시가 있고, 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 각 M개의 버스에 대해 '출발 도시, 도착 도시, 비용'이 주어진다. A 도시에서 B 도시로 가는 최소 비용을 구하자. 도시는 1부터 N까지의 자연수로 나타난다.

풀이 설명

출발 지점부터 도착 지점까지의 최소 비용을 구하는 것, 다익스트라(dijkstra) 알고리즘으로 예시 입출력 문제를 풀어보니, 다른 입력들에서도 답을 구할 수 있으리라 생각되었다.

visited를 활용한 다익스트라 구현

어제+그제 문제들을 풀면서 visited 배열을 사용하는 것이 비효율적인 중복 탐색을 방지하여 소요 시간 개선에 탁월하다는 것을 느껴서 오늘 다익스트라 문제도 동일하게 visited 배열을 활용하여 구현하고자 하였다.

from heapq import heappush, heappop
import sys
input=sys.stdin.readline

N=int(input().rstrip())
M=int(input().rstrip())
buses={}
for i in range(1, N+1):
    buses[i]=[]

for _ in range(M):
    start, end, cost=map(int, input().rstrip().split())
    buses[start].append((cost, start, end))

start, end=map(int, input().rstrip().split())
a_start, a_end=start, end
min_cost=[1000000000 for _ in range(N+1)]
visited=[[0 for _ in range(N+1)] for _ in range(N+1)]

min_cost[start]=0
heap=[(0, start, start)]
visited[start][start]=1

while heap:
    cost, start, end=heappop(heap)
    c_cost=cost+min_cost[start]
    if min_cost[end]<c_cost:
        continue

    for bus in buses[end]:
        n_cost, n_start, n_end=bus
        if visited[n_start][n_end]==1:
            continue
        elif visited[n_start][n_end]==0:
            if c_cost+n_cost<min_cost[n_end]:
                min_cost[n_end]=c_cost+n_cost
                heappush(heap, bus)
                visited[n_start][n_end]=1   

print(min_cost[a_end])

 

하지만, 결과는 틀렸습니다.

이번 문제에서 입력 조건 제한사항은 단순하게 visited를 사용할 수 없는 조건이었다. (버스 출발 도시, 버스 도착 도시, 소요 시간)의 형태로 입력되는 input에서 (버스 출발 도시, 버스 도착 도시)가 중복하여 입력될 수 있었기 때문이다.

이것이 왜 문제가 되냐면, 만약 아래와 같이 동일한 출발, 도착 도시 조건에서 소요 시간이 더 큰 것이 먼저 buses={}에 append된다면, 후에 소요 시간이 큰 버스 경로를 탐색한 후, 더 적은 소요 시간의 버스 경로를 탐색하지 않는다.

2
3
1 2 5
1 2 10
1 2 3
1 2

(이를 알게 된 질문 게시판의 게시물)

sorted로 buses의 배열 정렬한 후, 탐색하기

이 문제를 개선하기 위해서 각 출발 도시의 버스 경로를 cost 순으로 정렬한 후, 탐색하고자 하였다.

이론적으로는 맞긴하나, 시간 초과로 오답 처리되었다.

visited를 없앤 다익스트라를 구현

start 그래프 노드의 비용이 최소일 때, end 그래프 노드의 비용을 현재 최소 비용과 비교한 후 업데이트 하는 방식으로 visited를 사용하지 않되, 비효율적인 탐색을 방지하는 방식으로 코드를 구현하였고, 정답 처리되었다.

 

이 코드는 아래의 게시물의 코드로부터 많은 도움을 받았다!

from heapq import heappush, heappop
import sys
input=sys.stdin.readline

N=int(input().rstrip())
M=int(input().rstrip())
buses={}
for i in range(1, N+1):
    buses[i]=[]

for _ in range(M):
    start, end, cost=map(int, input().rstrip().split())
    buses[start].append((cost, start, end))

start, end=map(int, input().rstrip().split())
a_start, a_end=start, end
min_cost=[100000001 for _ in range(N+1)]

min_cost[start]=0
heap=[]
heappush(heap, (0, start, start))

while heap:
    cost, start, end=heappop(heap)
    c_cost=cost+min_cost[start]
    if min_cost[end]<c_cost:
        continue

    for bus in buses[end]:
        n_cost, n_start, n_end=bus
        if min_cost[n_end]>min_cost[n_start]+n_cost:
            min_cost[n_end]=min_cost[n_start]+n_cost    
            heappush(heap, bus)

print(min_cost[a_end])

[탐색/다익스트라] 백준 1916 최소비용 구하기 - 파이썬(Python)

 

+질문 게시판에, 반례로 올라온 것들 중, 문제 입력 조건에 맞지 않는 것들이 있었는데 그만큼 많은 나포함 많은 사람들의 문제의 입력 조건을 놓치게 되는 것 같다. 이번 문제도 오답으로 고생했던 것이 문제의 입력 조건을 놓쳤기 때문인만큼 만약 나의 코드가 틀렸다면, 입출력 예시를 고안하고 테스트해보자.

 

같은 알고리즘도 문제의 조건에 따라, 구현 요소의 채택/비채택이 달라진다.
제출 코드가 오답인 경우, 입력 조건을 기반으로 테스트해보자.