위상정렬

[백준] 1005 - ACM Craft (자바 Java)

[Gold III] ACM Craft - 1005 문제 링크 성능 요약 메모리: 301808 KB, 시간: 1948 ms 분류 다이나믹 프로그래밍(dp), 그래프 이론(graphs), 위상 정렬(topological_sorting) 문제 설명 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성..

[알고리즘] 위상 정렬 Topological Sort (자바 Java)

위상 정렬 사이클이 없는 유향 그래프 G=(V,E)에서 V의 모든 정점을 정렬 간선 (i, j)가 존재하면 정점 i는 반드시 j보다 앞에 위치 방식 1: 큐 활용 topologicalSort(G, V) { for i