[ 백준 ][ 플래5 ] 13308번 - 주유소 ( 파이썬 PYTHON ) ( 부분 성공 )

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

13308번: 주유소

 

코드

---

import heapq,sys
input=sys.stdin.readline

n,m = map(int,input().split())
price = [0]+list(map(int,input().split()))

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a,b,w = map(int,input().split())
    graph[a].append([b, w])
    graph[b].append([a, w])

def dijkstra():
    dp = [[1e9] * (max(price)+1) for _ in range(n+1)]
    dp[1][price[1]] = 0
    Q = []
    heapq.heappush(Q,(0,price[1],1))
    while Q:
        now_dist, now_cost, now = heapq.heappop(Q)
        if now == n:
            return now_dist
        if dp[now][now_cost] < now_dist:
            continue
        for next, next_dist in graph[now]:
            next_cost = min(price[next],now_cost)
            if dp[next][now_cost] > now_dist + (now_cost * next_dist):
                dp[next][now_cost] = now_dist + (now_cost * next_dist)
                heapq.heappush(Q,(now_dist + (now_cost * next_dist), next_cost, next))

print(dijkstra())

 

풀이

---

처음 만나는 '서브태스크' 문제이다.

서브태스크 문제는 일반적인 테스트 케이스와는 달리 문제 제작자가 조건을 걸고 조건마다 배점을 부여해서 결과적으로 코드가 몇점인지를 말해준다. 참고로 위의 코드는 1,3번 서브태스크를 완료하여 34점을 받았다.

 

사실 이 문제는 '소프트웨어 마에스트로' 14기 2차 코딩 테스트 때 만났던 로봇문제와 비슷하다.

물론 제대로 해결하지 못했었고 dp를 사용하지도 않았었다. 그 문제에서는 길을 지나는 동안에도 충전이 되는 조건이 있어서 더 까다로웠다.

 

이런 DP문제를 해결할 때 나에게 항상 어려운 부분은 DP테이블을 어떻게 설계할 것인가이다.

위 코드에서는 DP테이블을 [도시번호(x)][현재까지 방문한 주유소의 최소 충전 단위비용(y)] 2차원 배열로 설계하였고 저장되는 값은 현재까지의 비용의 합(w)이다.

다시 말하자면 현재 도시(x)에 도착하기까지 방문한 주유소 중 최소 충전 단위비용은 y이고 두 상황을 고려했을 때 현재까지의 비용의 합의 최소값은 w이다.

 

현재 도시번호만 저장해도 dp테이블을 만들 수 있지만 현재까지 방문한 주유소의 최소 충전 단위비용까지 함께 고려한 이유는 무엇일까?

이는 최소 충전 단위비용에 따라 앞으로 방문하거나 지금까지 방문한 도시까지의 비용이 달라지기 때문이다.

지금 위치에서 다음 위치로 나아갈 때는 주유소의 (충전 단위비용 x 다음 도시까지의 거리)의 비용이 발생한다. 이 때, 이 비용을 최소로 하기 위해서는 다음 도시까지의 거리는 일정하므로 충전 단위비용을 줄여야 한다.

 

또한 충전 단위비용을 최소로 하기 위해서는 지금까지 방문한 주유소 중 가장 단위비용이 적은 주유소를 고르면 된다.

예를 들어, 1 -> 2 -> 3 -> 4 순으로 도시를 방문하는데 만약 2의 단위비용이 가장 작다면 굳이 3에서 4까지 가는 기름을 충전할 필요없이 2에서 충전하면 되는 것이다. 

 

또한 문제에서 제공하는 그래프는 양방향이고 싸이클이 발생할 수 있다. 그래서 무한정 싸이클을 반복하는 것을 막기 위해서는 방문처리가 필요한데 이 최소 충전 단위비용을 기준으로 삼아서 다이내믹 프로그래밍을 사용하면 방문처리를 겸할 수 있다.

현재 방문한 도시를 이전에 탐색한 적이 있을 때 같은 최소 단위비용이라 하더라도 어떤 간선을 거쳤느냐에 따라 비용이 달라질 수 있다. 그 비용을 비교하여 작은 값으로 대체해준다면 최종적으로 해당 위치, 최소단위비용에서 최소 비용을 찾을 수 있다.

물론 이는 음의 싸이클이 없다는 가정하에 가능하다.

 

마지막으로 정답을 찾는 방법이다.

dp테이블은 설명했듯이 두가지 인덱스로 이루어져 있다. 여기서 정답을 찾는 방법은 당연히 dp[n]의 모든 값 중 최소인 값을 찾으면 된다.

어떤 최소 단위비용으로 마지막 도시를 방문했던간에 가장 최소 비용으로만 도달했으면 되기 때문이다.

하지만 시간을 좀 더 줄이는 방법이 있다.

바로 우선순위큐를 사용하는 방법이다. 다익스트라 알고리즘에 의거하여 우선순위큐를 사용하면 어떤 노드를 처음 만났을 때 그 상태가 바로 최소비용이 된다. 따라서 우선순위큐로 도시를 탐색하면 모든 dp테이블을 완성하지 않더라도 최소비용을 찾을 수 있다.

 

 

 

참고 블로그

https://peisea0830.tistory.com/127

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