반응형 위상정렬2 백준 1005] C++ ACM Craft(위상정렬) 해당 문제는 백준 사이트에서 풀 수 있습니다. www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 1. 문제 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓.. 2021. 2. 22. C++] 위상정렬 구현 및 설명 위상정렬은 각 노드들의 간선 개수를 구한 후 간선개수가 가장 적은 요소부터 순회하는 알고리즘입니다. 여기서 간선 개수란 각 노드마다 연결된 개수를 의미합니다. 간선 개수가 적은 요소들을 순회하기 때문에 한번에 원하는 지점까지 못가게 되는 특징이 있습니다. 위상정렬을 이용한 예제들은 주로 '게임 스킬트리, 우선순위에 대한 시간 문제 등...' 다양하게 사용되고 있습니다. 아래 그림을 통해 코드를 구현해 보겠습니다. 여기서 만약 A에서 E로 간다고 가정한다면 A는 B나 C를 거치고 D를 거처서 E로 가거나 혹은 D에서 F를 거처 E로 가게 됩니다. 즉, 노드 간선을 기점으로 모든 노드를 순서대로 거처가는걸 알 수 있습니다. 이 간선을 거처가는것이 하나의 조건이 될 수 있습니다. 아래는 구현 코드 입니다. #.. 2019. 9. 26. 이전 1 다음 728x90 반응형
