[BOJ-1005]ACM Craft

정말 예전에 시도하고서 계속 실패인 상태로 있었던 문제인데 

첫번째로 이 문제를 단순하게 아무생각없이 이렇게 하면 될 걸? 이러면서 코딩을 했었고

두번째로 응? 이렇게하면 되는데 왜 안돼지? 해서 질문에 올리기 까지 했었다...... 근데 지금 풀어보니 몇분채 안걸리고 풀 수 있었다. 

그 질문보면 진짜 그냥 바보네 뭐지 이사람 아무생각이 없나 싶을 정도..............;;; 

​일단은 문제의 규칙은 이러하다.

1. 스타크래프트 건물을 짓듯이 테크트리가 있다.

2. 이 테크트리를 따라서 이 건물을 지을 때 걸리는 시간을 출력하는 것.

위상정렬을 전에 아는분이 보라고 했었는데 

그때 바로 볼 껄 계속 안보다가 이제서야 봤다..... 생각나면 바로 해야겠다.....

위상정렬은 내가 이해하기에 간단히 말하면,

방향 그래프에서 사이클이 없고, 다른 정점(V1)에서 해당 정점(V2)로 들어오는 간선의 갯수가 0 인 것부터 탐색해 나아가는 방법으로 생각했다.

#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
 
typedef vector<int> vi;
typedef vector<bool> vb;
typedef stack<int> si;
const int S = 1010;
vi G[S];
vi in_link;
vi start;
vi cost;
vi total;
vb vis;
si stk;
int N, K, W;
void init() {
    in_link.clear();
    in_link = vi(N + 1, 0);
    cost.clear();
    cost = vi(N + 1, 0);
    total.clear();
    total = vi(N + 1, 0);
    vis.clear();
    start.clear();
    vis = vb(N + 1, false);
    for (int i = 1; i < S; i++) G[i].clear();
}
void dfs(int here) {
    vis[here] = true;
    for (auto there : G[here]) {
        if (!vis[there]) {
            dfs(there);                
        }
    }
    stk.push(here);
    
    return;
}
void process(int here) {
    for (auto there : G[here]) {
        if(total[there] < total[here] + cost[there]){
            total[there] = total[here] + cost[there];
        }
    }
    
}
int main() {
    int T;
    cin >> T;
    for (int tc = 0; tc < T; tc++) {
        cin >> N >> K;
        init();
        for (int i = 1; i <= N; i++) {
            cin >> cost[i];
        }
        for (int i = 0; i < K; i++) {
            int u, v;
            cin >> u >> v;
            G[u].push_back(v);
            in_link[v]++;
        }
        cin >> W;
        // input end
        for (int i = 1; i <= N; i++) {
            if (in_link[i] == 0) start.push_back(i);
        }    
        // 어떤 정점이든 무조건 dfs를 시작하는 게 아니라.
        // 들어오는 간선이 없는 즉, 자신이 시작이되는
        // 자신에게 들어오는 간선이 없는 정점부터 시작해야한다.
        // stack을 사용하려면!
        for (auto i : start) {
            dfs(i);
            total[i] = cost[i];
            while (!stk.empty()) {
                int here = stk.top(); stk.pop();
                process(here);
            }
        }                
        // topological sort (using stack)
        printf("%d\n", total[W]);
    }
    return 0;
}

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
 
typedef vector<int> VI;
typedef vector<VI> VVI;
 
int main(){
    int tc;
    for(scanf("%d",&tc); tc--; ){
        int numOfBuild, numOfRule;
        scanf("%d %d", &numOfBuild, &numOfRule);
        VVI building = VVI(numOfBuild+1, VI(3, 0));
        VVI adj = VVI(numOfBuild+1,VI(0,0));
        
        for(int i = 1 ; i <= numOfBuild ; i++) scanf("%d", &building[i][1]); 
        
        for(int i = 0 ; i < numOfRule ; i++){
            int u, v;
            scanf("%d %d", &u, &v);
            adj[u].push_back(v);
            building[v][0]++;
        }
 
        queue<int> Q;
        for(int i = 1 ; i <= numOfBuild ; i++){
            if(building[i][0] == 0){
                Q.push(i);
                building[i][2] = building[i][1];
            }
        }
 
        while(!Q.empty()){
            int here = Q.front(); Q.pop();
            
            for(auto iter = adj[here].begin() ; iter != adj[here].end() ; iter++){
                int there = *iter;
                if(building[there][2] < building[there][1] + building[here][2]){
                    building[there][2] = building[there][1] + building[here][2];
                }
 
                building[there][0]--;
                if(building[there][0] == 0) Q.push(there);
            }
        }
 
        int want;
        scanf("%d", &want);
        printf("%d\n", building[want][2]);
    }
    return 0;
}