백준 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 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

#include <iostream> #include <vector> #include <queue> using namespace std; int testCase; class Node{ public: int inDegree; int buildTime; vector<int> next; vector<int> before; Node(){ buildTime = 0; inDegree = 0; } }; int main(){ ios_base::sync_with_stdio(false); cin >> testCase; int ret[testCase] = {0, }; for(int tcase = 0; tcase < testCase; tcase++){ int n, k, target; cin >> n >> k; Node node[n+1]; for(int i = 1; i <= n; i++){ cin >> node[i].buildTime; } for(int i = 1; i <= k; i++){ int a, b; cin >> a >> b; node[a].next.push_back(b); node[b].inDegree++; node[b].before.push_back(a); } cin >> target; queue<int> q; //시작점 찾기 for(int i = 1; i <= n; i++){ if(node[i].inDegree == 0){ q.push(i); } } while(!q.empty()){ int curIndex = q.front(); q.pop(); for(auto it = node[curIndex].next.begin(); it != node[curIndex].next.end(); it++){ if(--node[*it].inDegree == 0){ //다음 노드의 inDegree를 깎은것이 0이면 q에 넣음 q.push(*it); } } //현재 노드는 이전노드의 buildTime중 가장 큰시간에 자신의 buildTime을 더함. if(node[curIndex].before.size() != 0){ int maxIndex = -1; int maxTime = -1; for(int i = 0; i < node[curIndex].before.size(); i++){ int index = node[curIndex].before[i]; if(node[index].buildTime > maxTime){ maxIndex = index; maxTime = node[index].buildTime; } } node[curIndex].buildTime += node[maxIndex].buildTime; } } //구해진 건문들 답을 배열에 넣음. ret[tcase] = node[target].buildTime; } for(int i = 0; i < testCase; i++){ cout << ret[i] << '\n'; } return 0; }