https://www.acmicpc.net/problem/1516
각 단계별로 시간(비용)이 있을 때, 위상 정렬을 할 수 있는 정보가 주어지는 경우이다.
입력을 받을 때, indegree를 모두 구하면서 입력을 받는다.
초기에 indegree가 0인 지점을 큐에 넣고 시작하는데, 이런 지점은 이전에 필요로 하는 단계가 없기 때문에, 그 지점의 비용이
그 지점까지 총 비용이 된다.
이후에는 위상 정렬을 진행하는데, 현재 단계까지의 총 비용은 확정이므로, 다음 단계의 총 비용을 구해준다. 이 때, 시간의 경우, 가장 오래걸리는 시간을 넣어줘야 한다.
이게 당연한 것이, 4번을 수행하기 위해 1번과 3번을 사전에 수행해야 한다고 해보자.
다른 조건이 없다는 가정하에, 1번과 3번중에서는 어떤 것을 먼저해도 상관이 없다.
그렇다면 예를들어 1번을 하는데에 3초가 걸리고, 3번을 하는데에 6초가 걸린다고 쳐보자. 그리고 4번만을 수행하는 데에는 5초가 걸린다고 하자.
1번을 볼 때, 1번 다음에 4번을 수행해야 한다는 것을 알고 있고, 이 시점에서 4번을 완수하기 위해서는 1번의 시간 + 4번의 시간이 필요하다.
1번을 하면서 동시에 3번도 수행할 수 있기 때문에, 앞서 구한 1번 시간 + 4번시간과 3번 시간 + 4번시간을 비교해서, 오래 걸리는 시간으로 갱신해줘야 한다.
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 | #include<iostream> #include<vector> #include<queue> using namespace std; int t[502], n, ind[502], done[502]; vector<int> v[502]; queue<int> q; void tpgSort() { for (int i = 1; i <= n; i++) if (ind[i] == 0) { q.push(i); done[i] = t[i]; } for (int i = 0; i < n; i++) { if (q.empty()) cout << "cycle\n"; int cur = q.front(); q.pop(); int Max = -1; for (int j = 0; j < v[cur].size(); j++) { ind[v[cur][j]]--; if (ind[v[cur][j]] == 0) q.push(v[cur][j]); //다음 단계 비용 = 현재 단계까지 총비용중 가장 오래걸리는 비용 + 다음 단계 비용 if (done[v[cur][j]] < done[cur] + t[v[cur][j]]) { done[v[cur][j]] = done[cur] + t[v[cur][j]]; } } } } int main(void) { cin >> n; for (int i = 1; i <= n; i++) { int time; cin >> time; t[i] = time; while (1) { int pre; cin >> pre; if (pre == -1) break; v[pre].push_back(i); ind[i]++; } } tpgSort(); for(int i = 1 ; i <= n ; i++ ) printf("%d\n", done[i]); return 0; } | cs |
'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글
| 백준 11438 LCA2 C++ (0) | 2019.08.15 |
|---|---|
| 백준 1197 최소 스패닝 트리 C++ (0) | 2019.08.15 |
| 백준 2056 작업 C++ (0) | 2019.08.15 |
| 백준 1766 문제집 C++ (0) | 2019.08.15 |
| 백준 2252 줄 세우기 C++ (0) | 2019.08.15 |