위상정렬(Topolosical Sort)

위상정렬 (Topological sort) 이란 어떠한 일을 하는 순서를 결정해주는 정렬이라고 할 수 있다. 간단하게 생각해보면 일의 우선순위를 결정하는 것이다.

코드로 살펴보도록 하자 

for(int i=0;i<num;i++){
    int a,b;
    scanf("%d %d" , &a, &b);
    v[a].push_back(b);
    arr[b] +=1;                 //자기자신으로 오는 간선의 개수를 저장해두는 배열
}
 
queue<int> q;
 
for(int i=1;i<=edge;i++){
    if(arr[i] == 0){            //자기자신으로 오는 간선이 없는 경우 push
        q.push(i);
    }
}
 
for(int i=1;i<=edge;i++){
    int x = q.front();
    q.pop();
    
    printf("%d " , x);
    
    for(int j=0;j<v[x].size();j++){ //연결성을 없애고 그 지점으로 오는 간선이 없는경우 push해준다.
        int y = v[x][j];
        arr[y] -=1;                 //연결성을 없애주는 부분 (자기자신으로 오는 간선의 개수를 줄여주는곳 )
        if(arr[y] == 0){        //자기가 수행하기 위해 전처리 될 과정이 없는 경우 push해준다.
            q.push(y);
        }
    }
}

https://www.acmicpc.net/problem/2252 가 위상정렬의 가장 기본적인 문제가 될 것이다.

그런데 ..... 만약 문제가 이렇게 바뀐다면 어떻게 구현을 해야할까??

3번 조건이 추가된 것이다. (최대나 최소를 우선적으로 처리해주는 경우) 이런 경우에는 그냥 큐가아닌 priority_queue를 통해 구현을 한다. 

priority_queue<int> pq;          //priority queue를 통해 구현을 하는경우가 많음.
 
for(int i=1;i<=edge;i++){
    if(arr[i] == 0){             //자기자신으로 오는 간선이 없는 경우 push
        pq.push(-i);             //작은걸 우선적으로 넣기위함
    }
}
 
for(int i=1;i<=edge;i++){
    int x = -pq.top();           //큐에서 가장 큰 수를 꺼내는 top
    pq.pop();
    printf("%d " , x);
    for(int j=0;j<v[x].size();j++){ //연결성을 없애고 그 지점으로 오는 간선이 없는경우 push해준다.
        int y = v[x][j];
        arr[y] -=1;             //연결성을 없애주는 부분 (자기자신으로 오는 간선의 개수를 줄여주는곳 )
        if(arr[y] == 0){
            pq.push(-y);
        }
    }
}

이런식으로 pq를 구현하고 -i를 넣어주는 형식(제일 작은걸 우선적으로 처리하기 위함)으로 구현하면 된다.