[c++] 알고리즘 그래프 - 위상 정렬 - 백준 - 줄 세우기 2252

위상 정렬이란?

위상 정렬이란 어떤 집합에서 원소들의 우선 순위 정렬이라고 할 수 있겠다. 

 

또한 위상정렬은 비순환 방향 그래프 즉 (DAG : Directed Acyclic Graph)에서 가능하다. 

즉 그래프를 이루는 노드들 간의 순환이 존재하지 않게 방향이 존재할 때 가능한 정렬이다. 

DAG

위와 같은 DAG그래프를 선형적 그래프로 변경하는 것을 위상정렬이라고 한다. 

위상정렬은 말 그대로 위상을 정렬한다는 뜻으로 이 정렬에는 각 노드들의 우선 순위가 중요하다. 

또한 우선 순위만을 고려하기 때문에 최종 결과 값이 여러 개가 될 수 있다. 

 

즉 위의 비선형 그래프는 다음과 같은 뜻을 내포한다. 

1보다는 0이 선행되어야한다.

1보다는 4가 선행되어야한다.

 

2보다는 1이 선행되어야한다.

2보다는 4가 선행되어야한다. 

 

즉 위에서 1의 경우는 0과 4가 모두 나왔을 때만 자신이 등장할 수 있고

2의 경우는 1과 4가 모두 등장했을 때 자신이 나올 수 있다. 

 

따라서 자신에게 향하는 선이 없을 때만 자신의 차례가 될 수 있는데 선이 없는 노드가 많을 경우도 존재하므로 위상정렬의 결과가 유일하지 않은 것이다. 

 

일반적으로 그래프 이론에서 자신을 가리키는 선을 InDegree라고 많이 나타낸다. 

 

직관적으로 그러면 위성정렬의 코드를 어떻게 작성해야할까?

 

1. 우선 모든 연결 정보를 저장하는 인접행렬(adjacency matrix)를 담당하는 배열 또는 벡터가 하나 필요할 것이다. 

2. 자신에게 몇 개의 화살표가 향하고 있는지를 저장할 inDegree배열 또한 필요할 것이다. 

 

그러면 처음 시작 점은 당연히 처음부터 자신에게 아무 화살표도 없는 노드 즉 InDegree[i]의 값이 0인 노드가 시작일 것이다.

 

그렇다면 그 노드 번호를 출력하고 인접 행렬에서 그 노드번호에 해당하는 노드가 가리키고 있는 화살표를 없애주어야 할 것이다.  ( 이 것은 inDegree배열에서 일어나는 일일 것이다. )

 

예시 문제 - 백준 줄 세우기 2252

문제

 

입 출력

전형적인 위상정렬 문제이다. 위의 코드 구현 내용을 그대로 구현하면 된다. 

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#define MAX 32000+2
int N,M;
vector <int> compare[MAX];
int inDegree[MAX];
void input() {
	scanf("%d %d" , &N, &M); // 학생 명 수
    
    for(int i=0; i < M; i++) {
    	int a, b;
    	scanf("%d %d", &a, &b);
        compare[a].push_back(b);
        inDegree[b]++;
    } // 입력 받는 대로 vector에 인접 행렬을 만들어주고 inDegree배열에 화살표를 추가해준다. 
}

void topologySort() {
	queue<int> q;
    for(int i=1; i <= N; i++) {
    	// 만약 자신에게 향하는 화살표가 존재하지 않는다면 작업 대기 큐에 푸쉬해준다.
    	if(inDegree[i] == 0) { 
        	q.push(i);
        }
    }
    if(q.size() == 0) return;
    while(q.size()){
    	int x = q.front(); // 가장 위에 있는 값을 탐색한다.
        q.pop();
        for(int j=0; j < compare[x].size(); j++){
        	//인접 행렬을 탐색하면서 inDegree행렬의 화살표를 줄여준다.
            inDegree[compare[x][j]]--;
            if(inDegree[compare[x][j]] == 0); q.push(compare[x][j]); // 줄였는데 얘도 0이 된다면 작업 큐에 넣어준다.
        }
    }
    for(int i=1;i <=N; i++){
    	printf("%d ", &result[i]);
    }
}

int main() {
	input();
    topologysort();
    
    return 0;
}