[2637] 장난감 조립

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

2637번: 장난감 조립

위상정렬 문제다.

 

풀이

처음 문제를 읽었을 때는 기본부품부터 완성품까지 위상정렬로 탐색하여 부품의 개수를 세는 방법으로 접근하였는데, 그렇게 되면 기본부품을 파악하기 힘들어진다.

 

따라서 완성품에서 기본 부품 순서로 위상정렬을 통해 접근하여 탐색하였다. 마지막 노드라면 해당 부품의 cost를 출력하는 방법으로 접근했다. 

 

부품의 비용을 담을 크기 N의 cost배열과, 간선정보를 (다음노드 번호, 비용) 형태로 담을 크기 N의 튜플배열을 생성. 진입차수가 0인 N번 노드를 시작으로 현재 cost X 다음 cost를 배열에 갱신하여 참색을 수행하였다. 입력 예제의 시나리오를 그림으로 표현하면 다음과 같다.

 

각 노드의 진입 차수, 실시간 비용, 그리고 마지막으로 출력할 정답 배열을 생성한다.

가장 첫 번째로 진입 차수가 0인 7번 노드 방문, 4번, 6번, 5번 부품의 비용을 갱신한다.

(현재 비용 * 간선 비용)을 통해 계산이 가능하다.

다음으로 진입 차수가 0인 6번 노드 방문. 탐색을 시작한다. 인접 노드의 비용을 갱신.

3번 노드를 방문. 이때 3번 노드의 경우 더 이상 탐색 가능한 인접 노드가 없다.

3번 부품을 생산하기 위한 다른 부품은 필요 없다는 뜻이므로 ans 배열에 해당 비용을 반영한다.

다음으로 진입 차수가 0인 4번 노드 방문. 마찬가지로 더 이상 탐색 가능한 인접 노드가 없으므로 현재 비용을 ans 배열에 반영한다.

다음으로 5번 노드 방문 인접 노드인 1번 노드와 2번 노드에 (현재 부품 비용 * 간선 비용)을 계산하여 cost배열에 값을 반영한다.

1번 노드 방문. 더 이상 탐색 가능한 노드가 없다. ans 배열에 현재 비용을 반영한다.

마지막으로 2번 노드 방문. 더 이상 탐색 불가능 하므로 ans 배열에 현재 cost를 반영한다.

완성된 ans 배열을 통해 0이 아닌 값들을 출력하면 정답이다.

 

정답 코드