위상정렬

jemin0619 2024. 4. 7. 00:38

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

2252번: 줄 세우기

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의

www.acmicpc.net

2024.04.07

별다른 테크닉 없이 위상정렬만 하면 되는 문제이다.

#include <bits/stdc++.h>
using namespace std;

queue<int> Q;
vector<int> graph[32'003];
vector<int> ans;
int degree[32'003];
int n,m;


int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    while(m--){
        int u,v; cin>>u>>v;
        graph[u].push_back(v);
        degree[v]++;
    }
    for(int i=1;i<=n;i++){
        if(degree[i]==0) Q.push(i);
    }
    while(!Q.empty()){
        int cur=Q.front(); Q.pop();
        ans.push_back(cur);
        for(int nxt : graph[cur]){
            degree[nxt]--;
            if(degree[nxt]==0) Q.push(nxt);
        }
    }
    for(int answer : ans) cout<<answer<<' ';
    return 0;
}

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

2623번: 음악프로그램

첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한

www.acmicpc.net

2024.04.07

위상정렬이 불가능할 경우 0을 출력해야 한다.

처음에 모든 노드에 대해 DFS를 돌면서 사이클 여부를 확인할까 생각했는데, 그것보다 vector에 답을 넣어놓고, vector의 size가 n이 아니면 0을 출력하게 하는게 낫다고 생각해 코드를 구현했다.

입력 형식이 더러워서 코드도 더럽다...

#include<bits/stdc++.h>
using namespace std;

int n,m;
vector<int> graph[1003];
vector<int> ans;
queue<int> Q;
int indegree[1003];

int main(){
	ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	cin>>n>>m;
    while(m--){
        int x; cin>>x;
        x--;
        int pre; cin>>pre;
        while(x--){
            int nxt; cin>>nxt;
            graph[pre].push_back(nxt);
            pre=nxt;
            indegree[nxt]++;
        }
    }
    for(int i=1;i<=n;i++){
        if(indegree[i]==0) Q.push(i);
    }
    while(!Q.empty()){
        int cur=Q.front(); Q.pop();
        ans.push_back(cur);
        for(int nxt : graph[cur]){
            indegree[nxt]--;
            if(indegree[nxt]==0) Q.push(nxt);
        }
    }
    if(ans.size()!=n) cout<<0;
    else{
        for(int answer : ans) cout<<answer<<'\n';
    }
    return 0;
}

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

21276번: 계보 복원가 호석

석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다. 그러던 어느 날

www.acmicpc.net

2024.04.08

해시를 써야 할 것 같은 문제였다. 간만에 스스로 아이디어를 생각해내서 푼 문제여서 굉장히 뿌듯했다. 다 짜고 보니까 코드가 좀 더럽게 느껴지기도 하는데, 나중에 정해 코드와 비교하는 과정이 필요할 것 같다.

#include<bits/stdc++.h>
using namespace std;

set<string> name;
map<string,int> sti; //이름을 숫자로 매핑함
map<int,string> its;
vector<int> graph[1003];
int ind[1003]; //들어오는 간선 수
vector<int> anc; //가문 시조 이름 저장
set<int> child[1003]; //각 노드의 자식 저장
queue<int> Q;
int n,m,idx;

int main(){
	ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	cin>>n;

    //이름들을 Set에 저장해 정렬시킴
    for(int i=1;i<=n;i++){
        string str; cin>>str;
        name.insert(str);
    }

    //Set에 저장된 순서대로 매핑
    idx=1;
    for(string temp : name){
        sti[temp]=idx;
        its[idx++]=temp;
    }

    //정보를 읽고 그래프 생성
    cin>>m;
    while(m--){
        string u,v; cin>>u>>v;
        int iu=sti[u]; int iv=sti[v];
        graph[iv].push_back(iu);
        ind[iu]++;
    }

    //시조를 큐에 넣음
    for(int i=1;i<=n;i++){
        if(ind[i]==0) {Q.push(i); anc.push_back(i);}
    }

    //시조의 수와 이름을 출력함
    cout<<anc.size()<<'\n';
    for(int ancestor : anc) cout<<its[ancestor]<<' ';
    cout<<'\n';

    //위상정렬 시행
    while(!Q.empty()){
        int cur = Q.front(); Q.pop();
        for(int nxt : graph[cur]){
            ind[nxt]--;
            if(ind[nxt]==0) {Q.push(nxt); child[cur].insert(nxt);}
        }
    }

    idx=1;
    for(string temp : name){
        cout<<temp<<' ';
        cout<<child[sti[temp]].size()<<' ';
        for(int ch : child[sti[temp]]){
            cout<<its[ch]<<' ';
        }
        cout<<'\n';
        idx++;
    }
    return 0;
}

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

1766번: 문제집

첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주

www.acmicpc.net

2024.04.09

대놓고 위상정렬을 하라고 하는데, 쉬운 문제 우선으로 풀라고 한다. 우선순위 큐를 쓰라는 의도가 뻔하게 보이는 문제였다. 우선순위 큐의 최소 힙, 최대 힙에 대해 복습한 후 문제를 풀어보자.

#include <bits/stdc++.h>
using namespace std;

int n,m; //문제 수, 정보 수
int ind[32003];
vector<int> graph[32003];
priority_queue<int,vector<int>,greater<>> PQ;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    while(m--){
        int u,v; cin>>u>>v;
        graph[u].push_back(v);
        ind[v]++;
    }
    for(int i=1;i<=n;i++){
        if(ind[i]==0) PQ.push(i);
    }
    while(!PQ.empty()){
        int cur = PQ.top(); PQ.pop();
        cout<<cur<<' ';
        for(int nxt : graph[cur]){
            ind[nxt]--;
            if(ind[nxt]==0) PQ.push(nxt);
        }
    }
    return 0;
}

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

2056번: 작업

수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해

www.acmicpc.net

2024.04.10

간단한 DP 문제였다.

점화식은 잘 세웠는데, dp값의 갱신을 큐에 nxt를 넣으면서 해서 틀렸었다.

#include <bits/stdc++.h>
using namespace std;

int n;
int dp[10'003];
int len[10'003];
int ind[10'003];
vector<int> graph[10'003];
queue<int> Q;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        int l,num; cin>>l>>num;
        len[i]=l;
        while(num--){
            int x; cin>>x;
            graph[x].push_back(i);
            ind[i]++;
        }
    }
    for(int i=1;i<=n;i++){
        if(ind[i]==0){
            Q.push(i);
            dp[i]=len[i];
        }
    }
    while(!Q.empty()){
        int cur=Q.front(); Q.pop();
        for(int nxt : graph[cur]){
            ind[nxt]--;
            //dp값 갱신은 이동할 때가 아니라 만날 때마다 해줘야함
            dp[nxt]=max(dp[nxt],len[nxt]+dp[cur]);
            if(ind[nxt]==0){
                Q.push(nxt);
            }
        }
    }
    cout<<*max_element(dp,dp+n+1);
    return 0;
}

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

1005번: ACM Craft

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

www.acmicpc.net

2024.04.10

2056 작업과 같은 문제였다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t; cin>>t;
    while(t--){
        int n,k; cin>>n>>k;
        vector<int> graph[n+1];
        vector<int> len(n+1,0); //각 건물 건축에 걸리는 시간
        vector<int> ind(n+1,0);
        vector<int> dp(n+1,0);
        queue<int> Q;
        for(int i=1;i<=n;i++) cin>>len[i];
        while(k--){
            int u,v; cin>>u>>v;
            graph[u].push_back(v);
            ind[v]++;
        }
        for(int i=1;i<=n;i++){
            if(ind[i]==0){
                Q.push(i);
                dp[i]=len[i];
            }
        }
        while(!Q.empty()){
            int cur = Q.front(); Q.pop();
            for(int nxt : graph[cur]){
                ind[nxt]--;
                dp[nxt]=max(len[nxt]+dp[cur],dp[nxt]);
                if(ind[nxt]==0) Q.push(nxt);
            }
        }
        int x; cin>>x;
        cout<<dp[x]<<'\n';
    }
    return 0;
}

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

2637번: 장난감 조립

첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주

www.acmicpc.net

2024.04.10

위상 정렬은 위상 정렬 문제 티가 많이 난다. 위상 정렬 문제라는 것을 몰라서 틀릴 일은 없을 것 같다.

기본부품이 정해져있는 줄 알고 알고리즘을 짜서 틀렸고, Normal 배열에 기본 부품들을 저장해서 맞췄다.

답을 출력할 때 부품 번호를 출력해야 하는데 Normal 배열에서의 위치를 출력해서 틀렸었다.

구조적 바인딩이 정말 편하다.

#include <bits/stdc++.h>
using namespace std;
#define Pii pair<int,int>
#define X first
#define Y second

int n,m;
vector<int> Normal; //기본부품 저장
int ind[103];
int dp[103][103];
vector<Pii> graph[103]; //dp[n] n을 만드는데 기본 부품이 얼마나 필요한지 저장
queue<int> Q;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    while(m--){
        int x,y,k; cin>>x>>y>>k;
        //노드 y에서 x로 가는데 y가 k개 필요함
        graph[y].push_back({x,k});
        ind[x]++;
    }

    //기본 부품들을 큐에 넣음
    for(int i=1;i<=n;i++){
        if(ind[i]==0){
            Q.push(i);
            Normal.push_back(i);
            dp[i][i]=1;
        }
    }

    //위상정렬 시작
    while(!Q.empty()){
        int cur=Q.front(); Q.pop();
        for(int i=0;i<graph[cur].size();i++){
            auto [nxt,cnt] = graph[cur][i];
            ind[nxt]--;
            
            for(int i=0;i<Normal.size();i++){
                dp[nxt][Normal[i]]+=(dp[cur][Normal[i]]*cnt);
            }
            
            if(ind[nxt]==0) Q.push(nxt);
        }
    }
    
    for(int i=0;i<Normal.size();i++){
        cout<<Normal[i]<<' '<<dp[n][Normal[i]]<<'\n';
    }

    return 0;
}

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

1516번: 게임 개발

첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부

www.acmicpc.net

이런 간단한 위상정렬 문제가 많이 있어서 풀어보았다.

ACM Craft와 다를 바 없는 문제이다.

#include <bits/stdc++.h>
using namespace std;

int n;
int ind[503];
int len[503];
int dp[503];
vector<int> graph[503];
queue<int> Q;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>len[i];
        while(true){
            int x; cin>>x;
            if(x==-1) break;
            graph[x].push_back(i);
            ind[i]++;
        }
    }

    for(int i=1;i<=n;i++){
        if(ind[i]==0){
            Q.push(i);
            dp[i]=len[i];
        }
    }

    while(!Q.empty()){
        int cur=Q.front(); Q.pop();
        for(int nxt : graph[cur]){
            dp[nxt]=max(dp[nxt],len[nxt]+dp[cur]);
            ind[nxt]--;
            if(ind[nxt]==0) Q.push(nxt);
        }
    }

    for(int i=1;i<=n;i++) cout<<dp[i]<<'\n';
    return 0;
}