[백준/Baekjoon] 1005 ACM Craft C++ :: Topological Sort

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

1005번: ACM Craft

---

1. Logic

이 문제를 풀 때 중요한 키포인트는 두 가지 이다.

1. 1번 건물의 건설이 완료되어야만 2번과 3번 건물의 건설을 시작할 수 있다.

2. 2번과 3번의 건설을 동시에 진행 될 수 있다.

1번 건물의 건설이 다 끝나고 2번과 3번 건물을 건설하지만 3번 건물을 지을동안 2번 건물이 완성되더라도 아직 3번 건물이 다 안지어졌기 때문에 4번 건물을 짓지 못한다. 이 말은 항상 최대값을 갱신해 주면 된다는 말이다.

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n, k, w;

int dp[1001];
int Time[1001];
int inDegree[1001];
vector<int> input[1001];

void topologicalSort() {
    queue<int> q;
    for(int i = 1; i <= n; i++) {
        if(inDegree[i] == 0) {
            dp[i] = Time[i];
            q.push(i);
        }
    }

    while(!q.empty()) {
        int cur = q.front();
        q.pop();

        for(int i = 0; i < input[cur].size(); i++) {
            int next = input[cur][i];
            inDegree[next]--;
			
            // 최대값 갱신
            dp[next] = max(dp[next], dp[cur] + Time[next]);

            if(!inDegree[next]) {
                q.push(next);    
            }
        }
    }
}

void reset() {
    memset(dp, 0, sizeof(dp));
    memset(Time, 0, sizeof(Time));
    memset(inDegree, 0, sizeof(inDegree));

    for(int i = 0; i < 1001; i++) {
        input[i].clear();
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t;
    cin >> t;

    while(t--) {
        reset();
        cin >> n >> k;

        for(int i = 1; i <= n; i++) {
            cin >> Time[i];
        }

        for(int i = 0; i < k; i++) {
            int a, b;
            cin >> a >> b;
            input[a].push_back(b);
            inDegree[b]++;
        }

        cin >> w;
        
        topologicalSort();

        cout << dp[w] << "\n";
    }
}

 

 

---

3. Feedback

처음에 거꾸로 생각해서 어렵게 접근했지만 위상정렬을 돌면서 단지 최댓값만 갱신해주면 되는 문제였다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐