MultiStage Graph - Dynamic Programming

 

 위 그래프에서, V1에 위치한 노드 "1"이 V5에 위치한 노드 "12"까지 도달하는데까지 최소비용으로 갈 수 있는 경로를 찾으려고 한다. 물론 다익스트라 알고리즘을 통해 해결 가능하지만, DP 적 접근을 조명하여 문제를 해결해보고자 한다. 모든 내용은 맨 하단 남겨놓은 강의를 바탕으로 한다.

 "다이나믹 프로그래밍" 기법이 사용되기에 합당한 상황이란, 반복적으로 최적의 선택을 골라 답을 도출해야 하는 때 이다. 위 문제 역시 각 스테이지를 이동하며 최종적으로 가장 비용이 적게들게 하는 경로를 선택해야 하므로, DP에 대한 접근이 타당하다고 할 수 있다. 하지만 이전에 푼 백준 14501번 퇴사 문제와 마찬가지로, 최적의 경로를 찾아야 하는 상황이지만 그 최적의 경로라는 것이 최종적으로 봤을 때가 기준이라 마지막 스테이지인 V5부터 경우를 따져봐야 최적의 경로를 찾을 수 있다. 다음은 각 노드에서 최종 목적지까지의 최소 비용과 그 때 선택하는 다음 노드 번호를 담은 DP 테이블이다.

V	1	2	3	4	5	6	7	8	9	10	11	12
cost
d

 먼저 V5에 있는 노드 "12"가 V5까지 도달하는 최소 비용을 생각해보자. 비용은 자기 자신이기 때문에 0일 것이고, 선택하는 노드 역시 자기 자신이기 때문에 "12"일 것이다. 그리고 V4의 노드들이 V5까지 가는 최소 비용은 각각 4, 2, 5이다.

V	1	2	3	4	5	6	7	8	9	10	11	12
cost									4	2	5	0
d									12	12	12	12

 다음으로 V3에서 V5까지 가는 경우를 따져보자. 노드 "6"에서 V5 까지의 최소비용은, "9"로 이동하는 비용과 "9"에서 V5까지의 최소비용을 합한 값, 그리고 "10"으로 이동하는 비용과 "10"에서 V5까지의 최소비용을 합한 값을 비교하여 더 작은 쪽을 선택하면 될 것이다. 즉 현재 노드에서 다음 노드로 건너가는 비용 c(현재 노드, 다음 노드)와 다음 스테이지에 존재하는 어떤 노드가 최종 목적지 V5까지 가는데 지불해야하는 최소비용 cost(다음 스테이지, 어떤 노드)에 대해서 다음과 같은 수식을 얻을 수 있다.

$$ cost(3, 6) = min( c(6, 9) + cost(4, 9), c(6, 10) + cost(4, 10) ) $$

 결국 cost(3, 6)은 min( 6+4, 5+2 )로 7이 되며, 그 때 선택하는 노드는 "10"이므로 d = 10이다. 같은 방식으로 남아있는 다른 모든 노드에 대해 cost와 d를 구할 수 있다.

V	1	2	3	4	5	6	7	8	9	10	11	12
cost	16	7	9	18	15	7	5	7	4	2	5	0
d	2 or 3	7	6	8	8	10	10	10	12	12	12	12

 최종적으로 V1의 "1"에서 V5의 "12"까지 도달하는데 소요되는 최소비용은 16이며, 그 경로는 1 -> 2 -> 7 -> 10 -> 12 혹은 1 -> 3 -> 6 -> 10 -> 12 이라는 것을 알 수 있다. 다음은 예시를 구현한 코드이다.

코드

# 노드, 비용
c = [
  [],
  [(2, 9), (3, 7), (4, 3), (5, 2)],
  [(6, 4), (7, 2), (8, 1)],
  [(6, 2), (7, 7)],
  [(8, 11)],
  [(7, 11), (8, 8)],
  [(9, 6), (10, 5)],
  [(9, 4), (10, 3)],
  [(10, 5), (11, 6)],
  [(12, 4)],
  [(12, 2)],
  [(12, 5)],
  []]
stage = [[],[1],[2,3,4,5],[6,7,8],[9,10,11],[12]]

n = 12
cost = [0]*(n+1)
d = [0]*(n+1)
d[-1] = n

for i in range(len(stage)-2,0,-1):
  for j in stage[i]:
    min_value = int(1e9)
    # c(현재 노드, 다음 노드) + cost(다음 스테이지, 다음 노드)
    for idx,v in enumerate(map(lambda x : x[1] + cost[x[0]], c[j])):
      if v <= min_value:
        min_value = v
        d[j] = c[j][idx][0]
      cost[j] = min_value

print(cost)
print(d)

출력

[0, 16, 7, 9, 18, 15, 7, 5, 7, 4, 2, 5, 0]
[0, 3, 7, 6, 8, 8, 10, 10, 10, 12, 12, 12, 12]

 

출처

4.1.1 MultiStage Graph (Program) - Dynamic Programming - YouTube