백준 1005 acmcraft

백준 1005 acmcraft

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

startcraft 게임처럼, 빌드 순서가 주어진다. n개의 건물이 있고, 빌드 순서 간선은 k개가 있다고 하자.

그 n개의 건물들 중 순서도에 따라 지어가는 도중에 어떤 w 건물을 이기는게 확정된다고 한다.

이때 이길 수 있는 w 건물을 짓게되는 최소시간이 몇인가?

방법론 : 위상정렬 (topological sort) + 간단한 수학

위상정렬을 할 때 입차수가 0인 임의의 u노드를 현재 그래프에서 빼주는데,

이 때 남아있는 그래프에서 그 노드 u를 포함하고 있는 간선E가 연결된 나머지 노드 v에 대해 indegree를 뺴주는 것을 확실히 한다. 

여기 까지는 naive한 위상정렬 알고리즘으로 구현할 수 있다.

그런데 최소시간을 구해야한다.  

각 노드의 요구된 시간을 구해야하는데 기존에 입력받은 time 정보와 요구된 시간 배열 summation time 정보 배열을 사용한다. summation time은 우선 각 노드의 필요 수행시간을 저장해놓는다.

그 다음 임의의 노드 u를 빼줄 때 간선 E가 연결된 나머지 노드 v에 대해 indegree를 빼줄 때 그 작업을 할 때 동시에, 노드 v까지 도달할 때 걸리는 시간을 갱신해주는 작업을 할 수 있다.

시간의 갱신은 다음과 같이 표현할 수 있다.

summationtime[ v ] = max ( summationtime[ v ], summationtime[ v ] + time[ u ] );

왜냐하면 임의의 노드 v는 여러 번 갱신될 수 있지만 최장 시간을 보유해야하기 때문이다.

소스보기

https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/1005.cc