백준 2056 작업 C++

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

2056번: 작업

대회 문제를 풀어야 하는데 논문 읽기에 눈이 침침해서 하나 풀어봤습니다. (이것도 빨리 해야되는데....)

간단한 위상정렬 문제였습니다. 작업에 걸리는 시간과 선행 작업이 주어졌을 때 전체 작업에 걸리는 최소시간을 구하는 문제입니다. 작업은 동시에 진행이 가능합니다. (문제 예시 : 같은 시간에 3, 4번 작업 수행)

 

위상 정렬을 이용하여 선행 작업에 대한 차수를 구하고, 차수가 0일 때마다 우선순위 큐에 (이전 작업 + 현재 노드의 작업) 을 넣습니다. 마지막 큐의 원소의 작업 시간이 최종 시간입니다.

 

코드는 다음과 같습니다.