[백준] 1916번 최소비용 구하기 [Python] - 그래프 이론

도시의 수: N, 버스의 수: M와 정보: $($A -> B, 버스 비용$)$, 출발 도시: S, 도착 도시: E에 대한 정보가 주어질 때,

출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 구하는 문제

 

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

입력

첫째 줄에 도시의 개수 N$(1 ≤ N ≤ 1,000)$이 주어지고 둘째 줄에는 버스의 개수 M$(1 ≤ M ≤ 100,000)$이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

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

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

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

 

버스 정보를 저장하고 데이크스트라 알고리즘으로 풀 수 있다.

시간 초과를 피하기 위해서 우선 순위 큐를 사용할 수 있다.

 

버스 정보는 2차원 리스트나 딕셔너리 등에 저장해서 코드들 짜봤다.

 

데이크스트라 알고리즘은

A에서 B로 가는 경우의 비용과

A와 B 사이에 Node를 거쳐서 가는 경우의 비용을

비교해서 비용을 최솟값으로 업데이트 하는 알고리즘이다.

 

초기 비용을 아주 큰 값으로 설정해 두고, 시작점의 비용은 0으로 초기화 한다.

시작점과 연결된 모든 점에 대해서 위 알고리즘을 적용해서 비용을 업데이트 한다.

업데이트 된 도착 지점과 비용을 큐에 저장한다.

연결된 모든 점에 대해서 탐색이 끝나면,

큐에 남아있는 지점들 중에서 최소 비용으로 갈 수 있는 지점을 새로운 시작점으로 위 과정을 반복한다.

$($최소 비용의 지점을 우선 탐색해서 불필요한 업데이트를 줄이게 된다.$)$

 

위와 같이 탐색할 수 있는 자료 구조가 우선 순위 큐 구조이다.

위 구조를 구현하기 위해서 heapq를 이용해 큐를 heap처럼 사용했다.

 

• 딕셔너리

from sys import stdin
from heapq import heappush, heappop
input = stdin.readline
INF = float('INF')

def dijkstra(graph, s, e, N):
    costs = [INF]*(N+1)
    q = []
    heappush(q, (0, s))
    costs[s] = 0
    while q:
        s_cost, node = heappop(q)
        if costs[node] < s_cost: continue
        # if node == e: break
        for dst, d_cost in graph[node].items():
            d_cost += s_cost  # costs[node]
            if d_cost < costs[dst]:
                costs[dst] = d_cost
                heappush(q, (d_cost, dst))
    print(costs[e])

def main():
    N = int(input())
    M = int(input())
    graph = [{} for _ in range(N+1)]
    for _ in range(M):
        s, e, c = map(int, input().split())
        # graph[s][e] = min(graph[s].get(e, INF), c)
        if e in graph[s]:
            graph[s][e] = min(graph[s][e], c)
        else:
            graph[s][e] = c
    s, e = map(int, input().split())
    dijkstra(graph, s, e, N)

if __name__ == "__main__":
    main()

 

 

• 2차원 리스트

from sys import stdin
from heapq import heappush, heappop
input = stdin.readline
INF = float('INF')

def main():
    N = int(input())
    M = int(input())

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

    for _ in range(M):
        s, e, c = map(int, input().split())
        graph[s].append((e, c))

    def dijkstra(s, e):
        q = []
        heappush(q, (0, s))
        costs[s] = 0
        while q:
            s_cost, node = heappop(q)
            if costs[node] < s_cost: continue
            if node == e: break
            for dst, d_cost in graph[node]:
                d_cost += s_cost
                if d_cost < costs[dst]:
                    costs[dst] = d_cost
                    heappush(q, (d_cost, dst))

        print(costs[e])

    s, e = map(int, input().split())
    dijkstra(s, e)

if __name__ == "__main__":
    main()

 

 

시간 초과 << 기본 데이크스트라 알고리즘

from sys import stdin
input = stdin.readline

INF = float('INF') # 10**5
N = int(input())
graph = [[INF]*(N+1) for _ in range(N+1)]

M = int(input())
for _ in range(M):
    s, e, c = map(int, input().split())
    graph[s][e] = c

for node in range(1, N):
    for i in range(1, N):
        for j in range(1, N+1):
            graph[i][j] = min(graph[i][j], graph[i][node] + graph[node][j])

s, e = map(int, input().split())
print(graph[s][e])

 

 

예제 입력 1 

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

예제 출력 1 

4