백준 1005번. ACM Craft (Java)

문제 링크 : https://www.acmicpc.net/problem/1005

건물의 빌드 순서를 정해줄 때 특정 건물을 짓기 위해 총 소요되는 시간을 구하는 문제입니다.

DFS로 해당 건물에 도달하기 위한 모든 경우를 탐색하는 방법도 있지만

방향을 갖고 사이클이 없다는 DAG 특성을 이용하여 위상 정렬을 사용하였습니다.

위상 정렬에 대한 포스팅 https://bcp0109.tistory.com/21

일반적인 위상정렬과 다른 점은 노드의 순서가 아니라 소요 시간을 기억해야한다는 점입니다.

result 배열을 따로 만들어서 총 소요시간을 저장해둡니다.

1. 처음 indegree 가 0 인 건물들은 이전 테크가 없기 때문에 총 소요시간이 d[i] 입니다.

2. Queue에서 건물을 빼면서 해당 건물과 연결된 다른 건물들의 result 를 갱신해줍니다.

3. 이전까지의 소요시간 result[node] + 현재 건물의 소요시간 d[i] 로 이루어지며 이전 테크가 전부 올라가야 현재 건물을 지을 수 있기 때문에 가장 오래 걸리는 시간으로 갱신해줍니다.