(C++) - 백준(BOJ) 2252번 : 줄 세우기

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

2252번: 줄 세우기

 

위상정렬 문제였습니다.

 

풀이방법

 1. 단 방향그래프로 만듭니다.

 

 2. dfs를 수행하면서 모두 호출한 후에는 stack에 정점을 push해줍니다.

 

 3. 모든 원소를 stack pop하면서 출력합니다.

 

Code

indegree이용하는 법

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N,M,u,v,ins[32001];
vector <int> a[32001];
queue <int> q;
int main() {
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        cin >> u >> v;
        a[u].push_back(v);
        ins[v]++;
    }
    for (int i = 1; i <= N; i++)
    {
        if (ins[i] == 0)
            q.push(i);//후순위에 있는 학생들을 제외하고 학생 키 순으로 큐에 넣음
    }
    for (int i = 0; i < N; i++)
    {
        int x = q.front();
        q.pop();
        cout << x << ' ';//체크하며 출력
        for (int j = 0; j < a[x].size(); j++)
        {
            ins[a[x][j]]--;//ins의 인덱스 안에 값이 남아있으면 그 인덱스 번호의 학생은 후순위에 배치된다.
            if (ins[a[x][j]] == 0) { q.push(a[x][j]); }
        }
    }
}

 

stack이용하는 법

#include <bits/stdc++.h>
using namespace std;
int n,m;
int indegree[40000], ck[40000];
vector <int> graph[40000];
stack <int> st;

void dfs(int x){
    ck[x] = 1;
    for(auto g : graph[x]){
        if(ck[g]) continue;
        dfs(g);
    }
    st.push(x);
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }
    for(int i = 1; i <= n; i++){
        if(!ck[i]) dfs(i);
    }
    
    while(!st.empty()) cout << st.top() << ' ', st.pop();
}