Algorithm/Baekjoon

[Algorithm]Baekjoon 1005번 : AMC Craft

MaxLevel 2023. 10. 16. 01:58

https://www.acmicpc.net/problem/1005

 

1005번: ACM Craft

첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부

www.acmicpc.net

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
int t, n, k, d, x, y, w;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t;
 
    vector<int> answers;
 
    for (int i = 0; i < t; ++i)
    {
        cin >> n >> k;
 
        vector<vector<int>> graph(1001);
        int times[1001] = { 0 };
        int maxWeights[1001] = { 0 };
        int inDegrees[1001] = { 0 };
 
        for (int j = 1; j <= n; ++j)
        {
            cin >> times[j];
            maxWeights[j] = times[j];
        }
 
        for (int j = 0; j < k; ++j)
        {
            cin >> x >> y;
 
            graph[x].push_back(y);
            ++inDegrees[y];
        }
 
        cin >> w;
 
        queue<int> q;
        for (int j = 1; j <= n; ++j)
        {
            if (inDegrees[j] == 0) q.push(j);
        }
 
        for (int j = 0; j < k; ++j)
        {
            if (q.empty()) break;
 
            int curNode = q.front();
            q.pop();
 
            for (int l = 0; l < graph[curNode].size(); ++l)
            {
                int nextNode = graph[curNode][l];
 
                maxWeights[nextNode] = max(maxWeights[nextNode], maxWeights[curNode] + times[nextNode]);
 
                if (--inDegrees[nextNode] == 0) q.push(nextNode);
            }
        }
 
        answers.push_back(maxWeights[w]);
    }
 
    for (auto& temp : answers)
    {
        cout << temp << endl;
    }
}
 
 cs

기본적인 위상정렬에 문제에서 요구하는 값을 구하는 코드를 살짝 섞기만 하면 되는 문제이다.

주어진 건물을 완성하기위해선 이전건물들이 전부 완성되어야해서, 어차피 이전건물들중에서 가장 시간이 오래걸리는 건물이 기준이 될 수 밖에 없다.

처음에는 DFS로 풀었는데 70%? 정도에서 시간초과가 나왔다. 나름 DP에 업데이트하면서 했는데 그래도 불필요한 탐색이 있어서 그런 것 같다.

 

그래서 위상정렬로 풀었다. 키워드만 알고 실제로 적용해보는건 처음이였는데, 사실 코드가 굉장히 쉽다. 그러다보니 금방 문제에서 요구하는바를 해결하려면 어떤식으로 섞어야하는지 알 수 있었다. 

maxWeights는 해당 건물을 만들기 위한 최대시간들이다. 즉, maxWeights[건물번호]는 건물번호에 해당하는 건물을 완성하기까지의 최소시간이다.

말했듯이 결국 이전건물들의 건설시간 중 가장큰값이 기준이 되기때문에 큰값들을 업데이트해나가면 된다.