DAG, 위상정렬

Directed 방향

Acycllic 사이클이 없는
Graph 그래프

 

즉 DAG(사일클이 없는 방향 그래프)에서는

 

특수한 위상정렬이라는 알고리즘을 적용할 수 있습니다!

 

위상정렬은 어떤 일을 하는 순서를 찾는 알고리즘입니다.

 

예를 들면,

1을 해야 4를 할 수 있다.

1과 2를 모두해야 4를 할 수 있다.

그렇다면 1 2 4 순으로 일을 해야 합니다.

 

DAG에서 indegree가 0이 되어야 일을 할 수 있습니다.

그러므로 큐에 indegree가 0이 되는 정점을 push하면서 정렬을 진행합니다.

bfs와 유사한 구조를 가져요 :)

 

들어오는 간선 : indegree

나오는 간선 : outdegree

 

문제를 풀면서 이해해 봅시다!

 

처음에는 들어오는 간선이 0인 정점을 큐에 넣고 시작합니다.

큐 : 1 2 3

1을 꺼내면서 4와 9에 들어오는 간선의 수를 줄입니다.

이 때 9의 들어오는 간선의 수가 0이 되기 때문에 큐에 넣어줍니다.

순서 : 1

큐 : 2 3 9

2를 꺼내면서 4에 들어오는 간선의 수를 줄입니다.

이때 4의 들어오는 간선의 수가 0이므로 큐에 넣어줍니다.

순서 : 1 2

큐 : 3 9 4

3을 꺼내면서 5의 들어오는 간선의 수를 줄입니다.

이때 5의 들어오는 간선의 수가 0이므로 큐에 넣어줍니다.

순서 : 1 2 3

큐 : 9 4 5

9는 연결된 간선이 없으므로 큐에서 꺼내 줍니다.

순서 : 1 2 3 9

큐 : 4 5

4를 꺼내면서 7에 들어오는 간선의 수를 줄입니다.

들어오는 간선의 수가 0인 정점이 없으므로 큐에는 아무것도 들어가지 않습니다.

순서 : 1 2 3 9 4 

큐 : 5

5를 꺼내면서 7과 6의 들어오는 간선의 수를 줄입니다.

이때 7의 들어오는 정점의 수가 0이므로 큐에 넣습니다.

순서 : 1 2 3 9 4 5

큐 : 7

7을 꺼내면서 6과 8의 들어오는 간선의 수를 줄입니다.

이 때 6의 들어오는 간선의 수가 0이므로 큐에 넣습니다.

순서 : 1 2 3 9 4 5 7

큐 : 6 

6을 꺼내면서 8의 들어오는 간선의 수를 줄입니다.

이 때 8의 들어오는 간선의 수가 0이므로 큐에 넣습니다.

순서 : 1 2 3 9 4 5 7 6

큐 : 8

8을 꺼내면 정렬이 완료!

순서 : 1 2 3 9 4 5 7 6 8

 

//ind[i] : 정점 i의 in-degree

for (int k=0; k<n; k++) 
{
	int x = q.front();

	q.pop();

	cout << x;

	for (int i=0; i<a[x].size(); i++) 
    {
		int y = a[x][i];
		
        //들어오는 간선의 수를 줄인다.
		ind[y]--;
		
        //들어오는 간선의 수가 0이면 큐에 push
		if (ind[y] == 0)
        {
			q.push(y);
		}
        
        // bfs일 경우는 방문체크
        //if( check[y] == false ) 
        //{
		//q.push(y);
		//check[y] = true;
        //}
	}
}

 

예시 문제 1 : https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{
    cin.tie(NULL);
    std::ios::sync_with_stdio(false);

    int n,m;

    cin >> n >> m;

    vector<int> ind;
    vector<vector <int> > v;
    v.resize(n+1);
    ind.resize(n+1);

    for(int i=0;i<m;i++)
    {
        int a,b;
        cin >> a >> b;

        v[a].push_back(b);
        ind[b]++;
    }

    queue<int> q;

    //들어오는 간선의 수 0이면 push
    for(int i=1;i<=n;i++)
    {
        if(ind[i] == 0)
            q.push(i);
    }

    for(int i=1;i<=n;i++) {

        if (q.empty())
            cout << "cycle";

        int x = q.front();

        q.pop();

        cout << x << " ";

        //들어오는 간선 수 줄이고 0일때 push
        for (auto i : v[x]) {
            ind[i]--;
            if (ind[i] == 0)
                q.push(i);
        }
    }

    return 0;
}

 

 

예시 문제 2 : https://www.acmicpc.net/problem/1766

1766번: 문제집

이 예시는 위의 문제와 동일하지만 숫자가 작은 정점부터 꺼내야 해서 우선순위 큐를 사용해야 한다는 차이점이 있습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;

int main()
{
    cin.tie(NULL);
    std::ios::sync_with_stdio(false);

    int n,m;

    cin >> n >> m;

    vector<vector <int> > v(n+1);
    vector<int> ind(n+1);

    for(int i=0;i<m;i++)
    {
        int pre,nxt;

        cin >> pre >> nxt;

        v[pre].push_back(nxt);
        ind[nxt]++;
    }

    priority_queue<int, vector<int>, greater<int> > q;

    //들어오는 간선이 0인 정점 push
    for(int i=1;i<=n;i++)
    {
        if(ind[i]==0)
            q.push(i);
    }

    //정점의 수 만큼 정렬
    for(int i=1;i<=n;i++)
    {
        int x = q.top();

        cout << x << " ";

        q.pop();

        for(auto j : v[x])
        {
            //들어오는 간선의 수 감소
            ind[j]--;
            //들어오는 간선의 수 0이면 push
            if(ind[j]==0)
                q.push(j);
        }
    }
    return 0;
}