백준 2252 줄 세우기- 위상정렬 개념공부, 큐를 이용한 위상정렬 (c++)

 

우선순위 큐 문제를 풀어보려고 했다가, 위상정렬 개념을 처음 들어봐서 공부도 하고, 문제도 풀어본 좋은 경험이 된 문제인 것 같다.

 

문제를 풀기 전에 위상정렬에 대한 개념을 위키피디아에서 공부했다.

위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환 유향 그래프(directed acyclic graph)여야 한다.

 

위상정렬의 수행과정

1. 자기 자신을 가리키는 변이 없는 꼭짓점을 찾음.
2. 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제
3. 아직 그래프에 꼭짓점이 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료시킨다.

 

출처 :https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC

 

 

 

자 그럼 이제 문제를 풀어보자. 

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

2252번: 줄 세우기

우선 트리 구조는 벡터를 활용해서 집어넣는다.

위상 정렬 문제도 bfs로 역시 접근하는데, '일반적인' bfs 문제와는 달리, 

visited(특정 노드의 방문 여부)로 큐에 push여부를 결정하는 것이 아니다.

 

위에 써놓은 단계들 처럼, 특정 노드가 '출발하는 노드' 즉 다시말해서, predecessor(부모 노드) 가 하나도 없어지지 않을 때까지는

큐에 집어 넣으면 안된다.

부모노드가 하나도 없음을 bfs를 통해서 확인하도록 하고, 그다음에 순서대로 프린트하면 된다.

#include <iostream>
#include <queue>
using namespace std;
const int MAX = 32001;
int N,M;
int numOfPredecessor[MAX];
vector<int> graph[MAX];
 
void bfs(){
    queue<int> q;
    for(int i=1; i<=N; i++){
        if(!numOfPredecessor[i]) {
            visited[i]=true;
            q.push(i);
        }
    }
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        cout<<cur<<" ";
        for(int i=0; i<graph[cur].size(); i++){
            numOfPredecessor[graph[cur][i]]--;
            if(!numOfPredecessor[graph[cur][i]])
                q.push(graph[cur][i]);
        }
    }
}
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for(int i=0; i<M; i++){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        numOfPredecessor[b]++;
    }
    bfs();
}