[백준/9446] 아이템 제작 (Python)

Problem : https://www.acmicpc.net/problem/9446

9446번: 아이템 제작

 

Difficulty : Platinum 4

 

Status : Solved

 

Time : 00:48:36

 

---

 

문제 설명

 

선영이는 최근에 "노리스 타워" 라는 게임을 시작했다. 게임에는 아이템 종류가 총 n개가 있다. 이 아이템은 모두 선영이의 캐릭터가 착용할 수 있다. 아이템은 1번부터 n번까지 번호가 매겨져 있다. 선영이는 1번 아이템을 제작하려고 한다.

아이템을 얻는 방법은 다음과 같이 두 가지가 있다.

 

• 아이템을 구매할 수 있다. i번 아이템의 가격은 ci원이다.
• 아이템을 제작할 수 있다. 총 m가지 제작방법이 있다. 서로 다른 두 종류의 아이템을 대장장이에게 갖다 주면, 대장장이는 무료로 결과 아이템을 전달해 준다.

 

선영이가 1번 아이템을 얻는데 필요한 돈의 최솟값을 구하는 프로그램을 작성하시오.

 

입력 및 출력

 

입력

 

첫째 줄에는 아이템 종류의 수 n과 제작 방법의 수 m이 주어진다. (1 ≤ n ≤ 10,000, 0 ≤ m ≤ 100,000)

둘째 줄에는 각 아이템의 가격 ci가 아이템 번호가 증가하는 순서대로 주어진다. (0 ≤ ci ≤ 109)

다음 m개 줄에는 제작에 필요한 아이템과 그 결과 아이템의 번호 ai, xi, yi가 주어진다. 대장장이에게 xi번과 yi번 아이템을 하나씩 가져다주면, ai번 아이템을 결과로 준다는 뜻이다. (1 ≤ ai, xi, yi ≤ n, ai ≠ xi, xi ≠ yi, yi ≠ ai)

 

출력

 

각 테스트 케이스마다 1번 아이템을 얻는데 필요한 돈의 최솟값을 출력한다.

 

입력 예시

 

5 3
5 0 1 2 5
5 2 3
4 2 3
1 4 5

 

출력 예시

 

2

 

 

---

 

풀이

 

맨 처음은 위상 정렬로 어떻게 되지 않을까? 는 생각이었다. 하지만 여지 없이 시간 초과.

 

위상 정렬을 떠올린 이유는

• 위상 정렬 특성상 m개의 조합을 통해 낮은 위상의 업데이트가 끝나면(즉 최적화가 완료됨) 높은 위상에 관여할 수 있기 때문이고
• 즉 전체 최적해(cost[1])가 마지막에 구해진다

는 이유에서였다. 하지만 본 제작식은 사이클이 존재할 수 있다는 점을 간과했다. 이를테면 1, 2번 아이템으로 3번 아이템을, 2, 3번 아이템으로 4번 아이템을, 3, 4번 아이템으로 1번 아이템을 조합할 수 있다고 했을 때, 단순한 위상 정렬로는 이 상황을 고려하지 못한다.

 

하지만 위상 정렬을 떠올렸던 원인. 즉 하위 조건의 최적화가 완료되었을 때 상위 조건의 최적화에 영향을 미친다를 깊게 생각하면, 문제의 해결책을 바로 떠올릴 수 있었다. 최적화된 값은 항상 모든 경우의 수보다 작거나 같으므로, 값(cost)을 우선순위로 우선순위 큐를 사용할 수 있겠다.

 

우선, 모든 아이템을 사는 경우를 전부 우선순위 큐에 저장한다. 그리고....

• 우선순위 큐에서 현재 아이템과, 현재 아이템을 얻는 데 사용된 총 코스트를 pop한다.
• 이 아이템이 재료로 사용되는 조합식을 검색한다.
  • 즉 이 아이템의 총 코스트 + 다른 하나의 재료 아이템의 코스트 > 현재 생성되는 아이템의 코스트라면, 업데이트하고 우선순위 큐에 저장한다. 
  • 만약 두 재료 아이템 조합이 최적해라면 영향을 끼칠 것이고, 그렇지 않다고 해도 생성되는 아이템의 코스트는 다른 조합을 통해서 최적화되거나, 혹은 최악의 경우 단순히 생성 아이템을 구매하는 코스트로 방문될 것이다.
• 즉 다익스트라와 성질이 동일하다.

 

 

풀이 코드

from heapq import *
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
cost = list(map(int, input().split()))
nxt_list = [[] for _ in range(N)]

for _ in range(M) :
  a, x, y = map(int, input().split())
  nxt_list[x-1].append((a-1, y-1))
  nxt_list[y-1].append((a-1, x-1))

q = []
for i in range(N) :
  heappush(q, (cost[i], i))

while q :
  c, n = heappop(q)
  for a, x in nxt_list[n] :
    if cost[a] > cost[x] + c :
      cost[a] = cost[x] + c
      heappush(q, (cost[a], a))

print(cost[0])

풀이 완료!