백준 1005 acmcraft

백준 1005 acmcrafthttps://www.acmicpc.net/problem/1005 startcraft 게임처럼, 빌드 순서가 주어진다. n개의 건물이 있고, 빌드 순서 간선은 k개가 있다고 하자.그 n개의 건물들 중 순서도에 따라 지어가는 도중에 어떤 w 건물을 이기는게 확정된다고 한다.이때 이길 수 있는 w 건물을 짓게되는 최소시간이 몇인가? 방법론 : 위상정렬 (topological sort) + 간단한 수학 위상정렬을 할 때 입차수가 0인 임의의 u노드를 현재 그래프에서 빼주는데,이 때 남아있는 그래프에서 그 노드 u를 포함하고 있는 간선E가 연결된 나머지 노드 v에 대해 indegree를 뺴주는 것을 확실히 한다. 여기 까지는 naive한 위상정렬 알고리즘으로 구현할 수 있다. 그런데..
알고리즘 문제/graph 2018. 2. 1. 15:31
1