1005 ACM Craft
알고리즘(위상정렬, DP)
1
2
3
4
1. 1516 게임개발과 비슷한 유형이다
2. 위상정렬하여 푼다. 단, 1516과는 다르게 목표건물을 지었다는게 확인되면 while문을 종료하고 출력해도 됨.
3. 단, 진짜로 위상정렬한 배열을 만들 필요는 없고, 위상정렬식으로 풀어도 시간은 비슷하다. 오히려 위상정렬을 굳이 안만드는 편이 더 빠를 수있다.
4. 더 빠르게 하는 방법은, 목표건물이 속한 그래프만을 검사하는 것.
기타
1
1. DP : 왜 알고리즘 분류에 DP가 들어갔나 했더만, 이미 검사한 거는 check표시하여 검사하지않고, 최댓값을 다음 노드로 계속 넘겨주는 형태가 DP인거 같다.
코드
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
#include <iostream>
#include <cstring>
#include <vector>
#define MAX_CRAFT 1000
using namespace std;
typedef struct Craft {
int time;
int timeTaken;
int before;
bool isChecked;
vector<int> next;
} Craft;
Craft craft[MAX_CRAFT];
vector<int> answer;
int main() {
int numOfTc;
cin >> numOfTc;
for (int i = 0; i < numOfTc; i++) {
memset(craft, 0, sizeof(craft));
//입력
int numOfCraft, numOfOrder, targetCraft;
cin >> numOfCraft >> numOfOrder;
for (int j = 0; j < numOfCraft; j++)
cin >> craft[j].time;
for (int j = 0; j < numOfOrder; j++) {
int temp, temp2;
cin >> temp >> temp2;
temp--;
temp2--;
craft[temp].next.push_back(temp2);
craft[temp2].before++;
}
cin >> targetCraft;
targetCraft--;
//계산
bool check = true;
while (check) {
for (int j = 0; j < numOfCraft; j++) {
if (!craft[j].isChecked && craft[j].before == 0) {
int tempTime = craft[j].time + craft[j].timeTaken;
for (int k = 0; k < craft[j].next.size(); k++) {
if (craft[craft[j].next[k]].timeTaken < tempTime)
craft[craft[j].next[k]].timeTaken = tempTime;
craft[craft[j].next[k]].before--;
}
craft[j].isChecked = true;
if (j == targetCraft)
check = false;
}
}
}
answer.push_back(craft[targetCraft].time + craft[targetCraft].timeTaken);
}
for (int i = 0; i < answer.size(); i++)
cout << answer[i] << endl;
}