BOJ 문제풀이/위상정렬 (Topological Sort) 썸네일형 리스트형 백준 1516 : 게임 개발 https://www.acmicpc.net/problem/1516 순차적으로 진행해야 하는 DAG그래프를 다룰 때 위상정렬을 생각할 수 있다. 건물을 짓는데 필요한 건설시간과 건물을 짓기 이전에 걸리는 건설시간을 분리했다. 위상정렬을 할때 건물을 짓기 이전에 걸리는 시간이 최대여야 하기 때문이다. 예를들어 a를 짓기위해 b 와 c가 지어져야 하는데 b는 짓는데 총합 10초이고 c는 총합 20초라면a건설을 시작할 수 있는 시기는 c가 완료된 20초에나 가능한 것이다. 이를 유의해서 건물짓기 이전에 걸리는 건설시간을 MAX로 갱신시켜주어야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 3.. 더보기 백준 3665 : 최종 순위 https://www.acmicpc.net/problem/3665 위상정렬 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93#include #include #include using namespace std; class Node{ public: int inDegree = 0; b.. 더보기 백준 1005 : ACM Craft https://www.acmicpc.net/problem/1005 위상정렬을 할때 단순히 나열하는 것이 아니라이전의 작업 - 예를 들면 해당 건물을 건설하는데 드는 최종 시간을 구함. - 을 모두 마친 후다음 작업을 할때도 쓰인다. 각 건물노드 마다 이전index와 다음 index를 저장하여 이전 index의 건물건설 시간 중가장 오래걸렸던 건설시간을 자신의 건설시간에 더해 현재 건물노드의 건설시간을 설정하는 방식으로구현하였음. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 .. 더보기 백준 2623 : 음악프로그램 https://www.acmicpc.net/problem/2623 위상정렬 기본문제.항상 어떤 행위의 선행순서가 정해져있는 경우 topological sort를 생각해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71#include #include #include using namespace std; int n, m; class Node{ public: int inDegree = 0; ve.. 더보기 백준 2637 : 장난감조립 https://www.acmicpc.net/problem/2637 위상정렬(Topological Sort) 를 활용한 문제.단순히 indegree를 사용해서 순서만 설정해주는 것이 아니라정해진 순서대로 진행하면서 상위 부품의 비용을 업그레이드 시켜주어야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77#include #include #include #inc.. 더보기 이전 1 다음