[14907] 프로젝트 스케줄링

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

14907번: 프로젝트 스케줄링

위상정렬로 접근한 문제다.

 

풀이

입력받은 정보를 기반으로 매 순간 비용의 최댓값으로 갱신하여 위상정렬 순서로 탐색한다. 이후 비용의 최댓값을 출력하면 된다.

각 노드의 진입차수와 노드의 비용 그리고 최종으로 출력할 ans 배열을 생성한다.

가장 먼저 진입차수가 0인 노드를 큐에 넣고 탐색을 시작. 이때 노드에 해당하는 ans는 해당 노드의 cost로 결정된다.

이후 탐색가능한 노드의 ans 값은 ans [현재노드] + cost [탐색가능 노드]와 ans [탐색가능 노드] 중 더 큰 값으로 갱신된다.

다음 탐색을 통해 ans [C]가 8+2의 값으로 갱신되는 모습이다.

다음 탐색으로 ans [E]의 값이 0에서 ans [D] + cost [E]의 값으로 경신.

C노드의 탐색으로 ans [E] 값이 기존보다 더 큰 값인 ans [C] + cost [E]의 값 14로 갱신된다.

이후 E의 진입차수가 0이므로 큐에 삽입되고 탐색이 이루어진다.

ans [F]의 값이 16으로 최종 경신된다.

마지막으로 F노드 방문. 더 이상 탐색가능한 노드가 없으므로 탐색 종료.

ans의 값 중 가장 큰 값을 출력하면 된다.

정답 코드