[백준] 2252 : 줄 세우기, 위상 정렬

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

2252번: 줄 세우기

 

위상정렬 문제이다.

 

위상정렬

사이클이 없는 방향 그래프 (= DAG)의 모든 노드를 순서대로 나열할 때 사용

=> 방향성 O, 순서 O, 사이클 X 

 

이 문제는 사람들의 키를 순서대로 정렬하여 줄을 세우기 때문에(순서O, 방향성 O, 사이클 X) 위상 정렬로 문제를 푼다.

위상 정렬 템플릿을 그대로 사용하면 풀리는 문제이다.

코드

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

int n, m, a, b; 
int indegree[32004];
vector<int> graph[100004];
vector<int> result;

void topologySort(){
    queue<int> q;
    // 진입차수가 0인 노드 큐에 집어넣기
    for(int i=1;i<=n;i++){
        if(indegree[i]==0) q.push(i);
    }
    // 큐가 빌때까지 반복
    while(!q.empty()){
        int now = q.front();
        q.pop();
        result.push_back(now);
        for(int i=0;i<graph[now].size();i++){
            int node = graph[now][i];
            indegree[node]-=1;
            if(indegree[node]==0) q.push(node);
        }
    }
}

int main(){
    //1. 입력받기
    cin >> n >> m;
    for(int i=0;i<m;i++){
        cin >> a >> b;
        graph[a].push_back(b);
        indegree[b]+=1;
    }
    // 2. 위상정렬 수행
    topologySort(); 
    //  3. 정답 출력
    for(int r:result) cout << r << " ";
}

 

풀이