[Python 3] BOJ - 13308 "주유소"

 # 문제 링크

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

13308번: 주유소

 

 # 풀이

 개인적으로 이 문제의 핵심은 다익스트라 알고리즘이라고 생각한다. 다만, 일반적인 다익스트라와는 다르게 상태 공간을 현재 정점의 번호가 idx, 현재 기름을 넣기 위해 드는 단위 비용을 cost일 때 드는 최소 비용인 2차원 상태 공간 d[idx][cost]라고 정의하자.

<그림 1. 임의의 그래프 중 일부>

 위 그림 1은 임의의 그래프 중 일부 정점과 간선을 나타낸 그림이다. 우선 i번째 정점를 생각해보자. 이 때 i는 시작점일 수도 있다. 현재 i번째에서 주유를 하게 되면 거리 당 드는 비용은 5가 된다. 그런데, i에 도달하기 위해서 거친 0개 이상의 정점이 반드시 있었을 것이다. 예를 들어 i번째 정점을 가기 위해 거친 정점이 3개라고 가정해보자. 이 때 각각의 주유소의 단위 비용이 1,10,3이라고 하자. 또한 그 중에서 i번째 정점에 도착하기 직전에 단위 비용 3을 이용하여 i번째 정점에 왔다고 하자.

 그렇다면, 현재 i번째에서 j 혹은 k로 이동하기 전에 반드시 각각의 거리만큼 주유를 해야 한다. 그렇기 때문에 i번째 정점에서 내릴 수 있는 의사결정은 현재 i번째 정점을 오기 위해 지불했던 단위 비용을 계속 쓸 것인가, 혹은 이 때까지 썼던 단위 비용 대신 현재 i번째 정점의 단위 비용을 쓸 것인가이다. 

 이 때, 첫번째 의사결정을 통해 정점 j로 간다고 가정해보자. 이 때 드는 비용은 단위 비용 X 거리이므로, 3 X 17 = 51임을 알 수 있다. 두번째 의사결정의 경우는 5 X 17 = 85이다. 문제에서 거리와 단위 비용 모두 양수이기 때문에 단위 비용이 적은 쪽을 선택해야 총 비용이 작아지는 것은 자명하다. 따라서, 애초에 정점 i를 올 때 선택할 수 있는 단위 비용들, 즉 1,10,3중 단위 비용이 1인 경우를 선택해야 비용이 최소가 된다.

 따라서, 현재 정점에서 다른 정점으로 이동할 때는 현재 기름을 넣기 위해 드는 단위 비용인 cost에 가야하는 거리인 next_dist를 곱한 만큼의 비용이 들고, 이것이 d[next][cost]보다 작을때만 상태 공간을 변경해야 한다. 또한, 상태 공간을 변경할때는 다음 정점의 단위 비용과 현재 정점의 단위 비용 중 더 작은 값으로 바꿔줘야 정답을 구할 수 있다

 

 # 코드

import sys, heapq

# dijkstra : 현재 정점이 idx, 현재 단위 비용이 cost일 때 n번째 정점까지 가기 위해 드는 최소 비용을 리턴하는 함수
def dijkstra():
    inf = 98765432109876543210
    # d : 상태 공간 배열
    d = [[inf] * (max(arr) + 1) for _ in range(n + 1)]
    q = []
    d[1][arr[1]] = 0
    heapq.heappush(q, (0, arr[1], 1))
    while q:
        # now_dist : 현재 드는 총 비용
        # now_cost : 현재 정점에서 다른 정점으로 갈 때 드는 단위 비용
        # now : 현재 정점
        now_dist, now_cost, now = heapq.heappop(q)
        # 도착 시 정답 리턴
        if now == n:
            return now_dist
        if d[now][now_cost] < now_dist:
            continue
        for (next, next_dist) in adj[now]:
            # next_cost : 다음 정점으로 도착해서 쓸 단위 비용
            next_cost = min(arr[next], now_cost)
            # 현재 총 비용이 다음 정점으로 가기 위해 드는 비용보다 작다면 우선순위 큐에 삽입
            if d[next][now_cost] > now_dist + now_cost * next_dist:
                d[next][now_cost] = now_dist + now_cost * next_dist
                heapq.heappush(q, (now_dist + now_cost * next_dist, next_cost, next))

# 입력부
n, m = map(int, sys.stdin.readline().split())
arr = [-1] + list(map(int, sys.stdin.readline().split()))
adj = [[] for _ in range(n + 1)]
for _ in range(m):
    a,b,c = map(int, sys.stdin.readline().split())
    adj[a].append((b,c))
    adj[b].append((a,c))
    
# 정답 출력
print(dijkstra())