백준: Class 5 - 1005: 위상 정렬 알고리즘(Topological sort)

</br> 1005번을 풀다 보니 시간 초과가 좀 나서, 찾아 보니 위상정렬이라는 게 있다고 한다. 그래서 한 번 공부해 보자.
</br>

위상정렬

    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        ind[b]++;
    }
    queue<int> q;
    for(int i = 1; i <= n; i++){
        if( ind[i] == 0 ) q.push(i);
    }
    while( q.size() ){
        int now = q.front();
        q.pop();
        for(int i = 0; i < v[now].size(); i++){
            int nx = v[now][i];
            ind[nx]--;
            if( ind[nx] == 0 ) q.push(nx);
        }
    }

대충 이런 식으로, 그래프를 입력 받으며 i에 연결된 것들의 개수를 ind[i]에 저장한다.

즉 j -> i라면 ind[i]++

만약 ind[i]가 0이라면 큐에 넣는다.
큐를 탐색한다. now에서 나가는 엣지를 다 없앤다고 보면 된다. 그렇게 해서 ind[nx]가 줄게 되는데, 만약 0이 된다면 또 큐에 넣어 준다.

now -> nx라면 ind[nx]--

큐를 탐색하며 방문하는 순서가 위상정렬된 순서다.
</br>

1005: ACM Craft

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

방법 1.

int func(int now){
    if( dp[now] != -1 ) return dp[now];
    int ret = 0;
    for(int i = 0; i < graph[now].size(); i++){
        ret = max(ret, func(graph[now][i]));
    }
    dp[now] = nums[now] + ret;
    return nums[now] + ret;
}

// in main()
    while( t-- ){
        int n, k, w;
        cin >> n >> k;
        for(int i = 1; i <= n; i++){
            graph[i].clear();
            dp[i] = -1;
        }
        for(int i = 1; i <= n; i++){
            cin >> nums[i];
        }
        for(int i = 0; i < k; i++){
            int a, b;
            cin >> a >> b;
            graph[b].push_back(a);
        }
        cin >> w;

        cout << func(w) << '\n';
    }

물론 위상정렬을 안 쓰고 시간 초과 안 나게 푸는 방법도 있다.
dfs와 dp의 결합
말보다는 예제로 보여주면

ex)
1
7 8
10 1 100 10 3 1 1
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
7
    2(1)        5(3)
  /     \      /    \
1(10)     4(10)     7(1)
  \     /      \    /
    3(100)      6(1)    (진행 방향 ->)

dp[7] = 1 + max(dp[5], dp[6])
dp[6] = 1 + dp[4]
dp[5] = 3 + dp[4]
dp[4] = 10 + max(dp[2], dp[3])
dp[3] = 100 + dp[1]
dp[2] = 10 + dp[1]
dp[1] = 10

dp 없이 그냥 dfs 하면 시간 초과 나고,
dp 값 초기화를 0으로 하면 시간 초과 난다(경험)
어디부터 시작해야 할 지 모르므로 거꾸로 시작한다.
</br>

방법 2. 위상 정렬

#include <bits/stdc++.h>

using namespace std;

vector<int> graph[1001];
int nums[1001];
int ind[1001];
int times[1001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while( t-- ){
        int n, k, w;
        cin >> n >> k;
        for(int i = 1; i <= n; i++){
            graph[i].clear();
            ind[i] = 0;
            times[i] = 0;
        }
        for(int i = 1; i <= n; i++){
            cin >> nums[i];
        }
        for(int i = 0; i < k; i++){
            int a, b;
            cin >> a >> b;
            graph[a].push_back(b);
            ind[b]++;
        }
        cin >> w;
        queue<int> q;
        for(int i = 1; i <= n; i++){
            if( ind[i] == 0 ) q.push(i);
        }
        while( q.size() ){
            int now = q.front();
            q.pop();
            times[now] += nums[now];
            for(int i = 0; i < graph[now].size(); i++){
                int nx = graph[now][i];
                ind[nx]--;
                times[nx] = max(times[nx], times[now]);
                if( ind[nx] == 0 ) q.push(nx);
            }
        }
        cout << times[w] << '\n';
    }
}

위에서 본 위상정렬을 사용한다.
times[]에 시간을 저장하는데, times[nx]는 이전 것들을 다 기다려 줘야 하기 때문에, 자신과 이전 것 중 맥스 값을 저장해야 한다.
</br>

---

이거 아니까 쏠쏠하다
</br>