프로그래밍

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

[난이도] Gold5
[유형] 위상정렬

[풀이]
위상정렬

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int N,M,ans[1001],inDegree[1001];
vector<int> adj[1001];
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        inDegree[v]++;
    }
    queue<int> q;
    for(int i=1;i<=N;i++) {
        if(!inDegree[i]) {
            q.push(i);
            ans[i]=1;
        }
    }
    int cur=2;
    while(!q.empty()){
        int sz=q.size();
        while(sz--){
            int qf = q.front();
            q.pop();
            for(auto nxt : adj[qf]){
                if(--inDegree[nxt]==0){
                    q.push(nxt);
                    ans[nxt]=cur;
                }
            }
        }
        cur++;
    }
    for(int i=1;i<=N;i++) printf("%d ",ans[i]);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/14567.cpp

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

[난이도] Gold2
[유형] 위상정렬

[풀이]
N(완성품을) 시작점으로 해서 위상정렬을 하면서 필요한 부품의 갯수를 곱해가면 답을 구할 수 있다.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N,M;
vector<pair<int,int>> adj[101];
int in[101],cnt[101];
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<M;i++){
        int x,y,k;
        scanf("%d%d%d",&x,&y,&k);
        adj[x].push_back({y,k});
        in[y]++;
    }
    vector<int> ans;
    queue<int> q;
    q.push(N);
    cnt[N]=1;
    while(!q.empty()){
        int cur=q.front(); q.pop();
        if(adj[cur].empty()){
            ans.push_back(cur);
        }
        for(auto p : adj[cur]){
            int nxt=p.first;
            int c=p.second;
            cnt[nxt]+=cnt[cur]*c;
            if(--in[nxt]==0) q.push(nxt);
        }
    }
    sort(ans.begin(),ans.end());
    for(auto k : ans) printf("%d %d\n",k,cnt[k]);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/2637.cpp

www.acmicpc.net/problem/2056

[난이도] Gold4

[유형] 위상정렬

[풀이]

위상정렬로 각 작업을 방문하면서 total 배열에 그 작업에 도착하기 까지의 시간을 기록하면 된다.

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int N,work[10001],total[10001],in[10001],ret;
vector<int> adj[10001];
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        int ac,pre;
        scanf("%d%d",&work[i],&ac);
        in[i] = ac;
        for(int j=0;j<ac;j++){
            scanf("%d",&pre);
            adj[pre].push_back(i);
        }
    }
    queue<int> q;
    for(int i=1;i<=N;i++) if(!in[i]) q.push(i);
    while(!q.empty()){
        int qf = q.front(); q.pop();
        ret = max(ret,total[qf]+work[qf]);
        for(auto nxt : adj[qf]){
            total[nxt] = max(total[nxt],total[qf]+work[qf]);
            if(--in[nxt]==0) q.push(nxt);
        }

    }   
    printf("%d",ret);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2056.cpp