위상정렬
-
[BOJ] 1516 게임 개발PS/BOJ 2020. 7. 15. 18:47
https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 알고리즘: 위상 정렬 시간복잡도: O(N^2) BOJ 1005 ACM Craft 와 동일한 문제다. 일의 순서가 정해져 있고, 선행되는 일이 완수되어야 뒷 일을 수행할 수 있다는 조건으로 위상 정렬을 떠올릴 수 있다. 더보기 // 1516 게임 개발 #include #include #include #define MAX(a,b) (((a)>(b))?(a):(b)) using namespa..
-
[BOJ] 1005 ACM CraftPS/BOJ 2020. 7. 15. 13:29
https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 알고리즘: 위상 정렬 시간복잡도: O(n^2) 접근: 1. 건물 짓는 순서가 정해져 있음. 2. 각각의 건물들은 선행 건물들이 모두 지어져야 건설 가능. Point: 순서, 선행(prev.) -> 위상 정렬 최종 시간복잡도: O(n^2) 더보기 #include #include #include #define MAX(a, b) (((a)>(b))?(a):(b)) using namespace s..