topological sort

위상 정렬은 그래프 내 사이클이 존재 하지 않는 경우에만 사용 할 수 있습니다.

자세한 소개는 위키백과에 있더군요.

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

대충 스타크래프트 테크트리나 여러 게임들의 스킬트리들을 생각하시면 됩니다.

 

1. 그래프 구성

2. indegree(들어오는 선)가 0인 지점을 큐에 추가한다.

3. 큐에서 하나 빼고 뺀 지점에서 갈 수 있는 경로에 있는 지점의 indegree를 1씩 감소시킨다.

4. 모든 지점의 indegree가 0이 될 때까지 2 ~3 과정을 반복한다.

 

알기 쉽게 라면 끓여 먹기 계통도를 예를 들어 보겠습니다.

진한 주황색은 큐에 들어 있는 데이터를 의미하고 연한 주황색은 처리된 동작들을 의미합니다.

또, 주황색 화살표는 삭제될 간선을 의미합니다.

결과를 출력할 때는 연한 주황색이 된 순서대로 출력하면 됩니다.

 

 

 

 

여기서 파란색 글씨의 indegree는 들어오는 간선의 수를 의미합니다.

따라서 indegree가 0인 경우 선행되어야 할 것들이 모두 끝난 상태라고 볼 수 있습니다.

 

 

 

시작하기 앞서 큐에 indegree가 0인 점들을 넣어 놓습니다.

큐에 그림의 네 지점들을 넣는 순서는 상관 없으므로

가스레인지 켜기, 라면봉지 까기, 찬밥 준비 순서로 큐에 넣겠습니다.

 

 

 

가스레인지를 켜봅시다.

가스레인지를 킨 다음 해야 할 일들의 indegree를 1개씩 줄여보니 물 끓이기의 indegree가 0이 되네요.

즉, 현재 물을 끓이기 위해 필요한 행동은 더 이상 없습니다.

앞으로도 이렇게 indegree를 줄이다가 0이 되는 경우에 한해 큐에 넣어 줍니다.

 

 

 

 

큐에 들어 있는 두 번째 데이터는 라면봉지 까기였습니다.

라면봉지 까기는 두가지 행동의 선행 동작이었네요. 이 두가지의 indegree를 각각 1씩 감소 시킵니다.

두 동작 모두 indegree가 1이 되었습니다. 즉, 두 동작 모두 선행되어야 할 동작이 1개씩 있다는 것을 의미합니다.

두 동작 이전에 물 끓이기 동작이 먼저 행해져야 합니다.

indegree가 0인 지점에 한해 큐에 넣어야 하므로 큐의 다음 데이터를 봅시다.

 

큐의 세 번째 데이터는 찬밥 준비 입니다.

라면 봉지 까기와 마찬가지로 밥 말기의 indegree를 1 줄여 보았지만

찬밥을 준비 해도 라면이 완성되지 않았다 보니 밥을 말지 못 하겠내요.

큐에 밥 말기 데이터를 넣으면 안됩니다.

 

 

큐의 네 번째 데이터는 물 끓이기 입니다.

물 끓이기는 세 가지 동작의 선행 동작 이네요. 세 동작의 indegree를 1씩 감소 시킵니다.

세 동작 모두 indegree가 0이 되므로써 큐에 집어 넣을 수 있게 되었습니다.

저는 계란 넣기, 면 넣기, 스프 넣기 순으로 큐에 집어 넣겠습니다.

 

앞에서 행했던 방식으로 일을 처리 합니다.

계란 넣기를 행하고 라면 완성의 indegree를 1 감소 시킵니다.

아직 라면 완성은 큐에 넣지 못 합니다. 

 

면 넣기를 행하고 라면 완성의 indegree를 1 감소 시킵니다.

아직도 라면 완성을 큐에 넣을 수 없습니다.

 

 

 

스프 넣기를 행하고 라면 완성의 indegree를 1 감소 시킵니다.

이제 라면 완성을 행하기의 선행 동작이 없으므로 큐에 집어 넣습니다.

 

 

 

라면이 완성 되었으니 밥을 말아요.

 

 

 

모든 일이 처리 되었습니다.

답을 출력할 때는 연한 주황색이 된 순서대로 출력하면 됩니다.

 

참고로 사이클이 있는지 없는지는 따로 확인 할 필요 없고

bfs 이후 처리한 데이터 수가 입력 받은 데이터와 다른 경우에 사이클이 있다고 생각하시면 됩니다.

 

 

입력(input.txt)

9 12
1 3
2 5
2 6
3 4
3 5
3 7
3 6
4 7
5 7
6 7
7 9
8 9

 

출력(output.txt)

1 2 8 3 4 5 6 7 9

> 소스 보기

└ 접기

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define MaxSize 110
FILE *fin=fopen("input.txt","r");
FILE *fout=fopen("output.txt","w");
vector<int> data[MaxSize];
int n,m,cnt_ind[MaxSize];
int queue[MaxSize],head,tail;
int cnt_ans,ans[MaxSize];
void input()
{
    int i,tx,ty;
    fscanf(fin,"%d%d",&n,&m);
    for(i=1; i<=m; i++)
    {
        fscanf(fin,"%d%d",&tx,&ty);
        data[tx].push_back(ty);
        cnt_ind[ty]++;
    }
}
void process()
{
    int i;
    for(i=1; i<=n; i++)
    {
        if(cnt_ind[i]==0)
        {
            queue[++tail]=i;
        }
    }
    while(head!=tail)
    {
        head++;
        ans[++cnt_ans]=queue[head];
        for(i=0; i<data[queue[head]].size(); i++)
        {
            cnt_ind[data[queue[head]][i]]--;
            if(cnt_ind[data[queue[head]][i]]==0)
            {
                queue[++tail]=data[queue[head]][i];
            }
        }
    }
}
void output()
{
    int i;
    if(head!=n)
    {
        fprintf(fout,"impossible");
        return;
    }
    for(i=1; i<=n; i++)
    {
        fprintf(fout,"%d ",ans[i]);
    }
}
int main()
{
    input();
    process();
    output();
    fcloseall();
    return 0;
}

[출처] [c/c++ 코드] 위상 정렬 (Topological Sort)|작성자 choyi0521