위상 정렬 (Topological Sort)

위상 정렬 (Topological Sort)

방탈출 게임을 한다고 생각해 보자.

우리는 메인 룸에 있는 3개의 자물쇠를 풀어야 탈출에 성공하고, 다음 단계의 탈출에 도전할 수 있다. 3개의 열쇠는 메인 룸과 연결된 3개의 방에 각각 하나씩 숨겨져 있다.

따라서, 메인 룸에서 나가기 위해서는 방 A, B, C 에서 열쇠를 모두 찾아야만 할 것이다. 단 열쇠를 찾는 순서는 영향을 주지 않는다.

또한 열쇠를 3개 모두 찾지 못하면, 다음 단계의 탈출에는 도전할 수 없을 것이다.

따라서 다음 단계의 탈출에 도전하기 위해서는 다음과 같은 순서를 따라야 한다.

(A방에서 열쇠를 찾음 - B방에서 열쇠를 찾음 - C방에서 열쇠를 찾음) - 메인 룸의 자물쇠를 모두 푼다 - 메인 룸에서 탈출 후 다음 단계에 도전

(A, B, C에서 열쇠를 찾는 순서는 어떻게 되어도 상관없다.)

 

위상 정렬(Topological Sort)은 방향 그래프 내의 정점들을 방향에 반대되지 않는 순서대로 나열하는 것을 말한다.

쉽게 말하면 선행 관계가 주어졌을 때, 모든 일을 수행하기 위한 올바른 순서를 구하는 과정이다.

방향 그래프의 A -> B 는 위상 정렬에서 "A가 수행되어야만 B를 수행할 수 있다" 는 의미로 이해한다.

 

진입 차수와 진출 차수 (Indegree and Outdegree)

진입 차수(Indegree)란, 방향 그래프의 한 정점에 대해 그 정점으로 들어오는 간선의 개수를 의미한다. 즉, 간선의 도착점이 그 정점인 것의 개수와 같다.

진출 차수(Outdegree)란, 방향 그래프의 한 정점에 대해 그 정점에서 나가는 간선의 개수를 의미한다. 즉, 간선의 출발점이 그 정점인 것의 개수와 같다.

위상 정렬에서는 한 정점에 대해, 그 정점에서 나가는 간선을 지나기 위해서는 반드시 그 정점으로 들어오는 간선을 모두 지나야 한다.

 

위의 방탈출 예시를 메인 룸 기준 그래프로 나타내면 위와 같다. 

방 A ~ C에서 열쇠를 찾은 경우 각각은 메인 룸에서 나가기 위한 조건 하나를 각각 만족하는 것과 같다. 따라서 이는 진입 차수에 해당하는 간선이며, 메인 룸의 진입 차수는 3이다.

 

동작 원리

다음과 같은 그래프에서 위상 정렬의 동작 원리를 살펴보자.

예제 그래프

 

위상 정렬에서 한 정점에서 나가는 간선을 지나기 위해서는 그 정점으로 들어오는 모든 간선을 지나야 한다고 했다.

따라서 위상 정렬은 다음과 같이 동작한다.

① 최초 그래프에서 진입 차수가 0인 정점들을 모두 큐(Queue)에 넣는다.

② 큐에서 한 정점을 꺼낸다.

③ 그 정점과 연결된 모든 정점에 대해 진입 차수를 1 뺀다.

④ 이 때 그 정점의 진입 차수가 0이 됐다면, 그 정점을 큐에 넣는다. (즉, 진입 차수가 0인 정점만 큐에 들어갈 수 있다.)

⑤ ② ~④를 큐가 빌 때까지 반복한다.

 

예제 그래프에서 최초 진입 차수가 0인 정점은 1 뿐이다. 따라서 큐에 1을 넣는다.

 

큐에서 1을 꺼내고, 1과 연결된 모든 정점에 대해 그 정점으로의 간선을 없앤다.

(즉, 연결된 모든 정점의 진입 차수를 1 감소시킨다.)

 

1과 연결된 간선을 없앰으로써 3번 정점의 진입 차수가 0이 되었다. 따라서 큐에 3을 넣는다.

 

큐에서 3을 꺼내고, 마찬가지로 3과 연결된 모든 정점들의 진입 차수를 1 감소시킨다.

 

이후 과정은 모두 동일하다.

예제 그래프에서 위상 정렬의 결과는 1 - 3 - 2 - 4 - 5 - 6 - 7 로, 이는 곧 진입 차수를 정점에 대한 조건으로 생각했을 때 모든 조건을 만족하게 되는 정점의 순서와도 같다.

 

사이클이 존재하는 경우

그래프 내에서 사이클이 존재하면 경우 위상 정렬을 적용할 수 없다.

그래프에서 사이클이 발생할 경우, 그 사이클이 발생한 정점은 감소시킬 수 없는 진입 차수를 갖게 되므로 위상 정렬의 진행이 멈추게 된다.

위 그림에서 4번 정점에서 2번 정점까지의 간선은 위상 정렬 내에서 절대로 지나갈 수 없다.

 

구현

위상 정렬은 그래프 탐색인 BFS와 유사한 방식으로 구현할 수 있다.

BFS로 구현할 경우, 진입 차수가 0일 때만 큐에 삽입하도록 조건을 걸어준다면 쉽게 구현 가능하다.

큐에서 정점을 꺼낸 후 그 정점에서 나가는 간선을 지우는 것은 다소 구현이 복잡하므로, 각 정점의 진입 차수를 저장한 indegree[] 배열의 값만 감소시키도록 구현했다.

코드

void topological_sort() {
    queue<int> que;
    //최초 그래프에서 진입 차수가 0인 정점을 삽입
    for (int i = 1; i <= 7; i++)
        if (indegree[i] == 0) que.push(i);
 
    while (!que.empty()) {
        int cur = que.front();
        que.pop();
 
        printf("%d ", cur);
 
        //큐에서 꺼낸 정점과 연결된 모든 정점에 대해
        for (int i = 0; i < adj[cur].size(); i++) {
            int nextnode = adj[cur][i];
            //그 노드의 진입차수를 1 감소
            indegree[nextnode]--;
 
            //만약 그 노드의 진입차수가 0이 되었다면, 조건을 모두 만족했으므로 나아갈 수 있음
            //따라서 큐에 삽입한다.
            if (indegree[nextnode] == 0) que.push(nextnode);
        }
    }
}

 

 

위상 정렬을 응용한 문제

위상 정렬은 어떠한 Task들 간의 먼저 이행되어야하는 순서가 존재할 때, 이를 올바른 순서로 진행하기 위해 사용된다.

따라서 알고리즘 문제에 응용될 때, 선행 관계 등이 제시될 경우 위상 정렬 문제로 접근할 수 있다.

 

연습 문제

BOJ 1766 문제집  : www.acmicpc.net/problem/1766

1766번: 문제집