[백준/C++] 2252번 줄세우기

1.문제 링크

줄세우기

2. 풀이 전 계획과 생각

• 위상정렬 알고리즘

3. 풀이

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

vector<int> graph[32001];
int indegree[32001];

int result[32001];

int n;

void topology_sort(){
    queue<int> q;

    for(int i=1;i<=n;i++){
        if(indegree[i]==0) q.push(i);
    }

    while(!q.empty()){
        int now = q.front();
        q.pop();
        cout<<now<<' '; 

        for(int i=0;i<graph[now].size();i++){
            indegree[graph[now][i]]-=1;
            if(indegree[graph[now][i]]==0){
                q.push(graph[now][i]);
            }
        }
    }
}

int main(){
	int m;
	cin>>n>>m;
	
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		graph[a].push_back(b);
		indegree[b]+=1;
	}
	
	topology_sort();
	
}

전형적인 위상정렬 알고리즘이다.

q에서 pop 하기 전에 큐에 들어있는 front 원소를 출력하면 된다.

4. 풀이하면서 고민했던 점

5. 문제를 풀고 알게된 개념 및 소감

-