위상 정렬이 무엇일까?

directed acyclic graph에만 적용할 수 있는 정렬 방법으로 edge uv에 대해 u 이후에 v가 위치하도록 정렬하는 방법이다.
예를 들어 아침 일과를 그래프로 표현했다고 가정하자.
아침 운동-->아침밥-->양치
아침 운동-->영양제 섭취
이 그래프에 대해 위상 정렬을 실시하면 '아침운동, 아침밥, 양치, 영양제 섭취'가 될 수 있다.
모든 arrow에 대해 u 이후에 v가 온다는 조건을 만족하기 때문이다.
혹은 '아침 운동, 아침밥, 영양제 섭취, 양치'가 될 수도 있다.
이 경우도 위상 정렬의 조건을 만족한다.
이처럼 위상 정렬의 결과는 하나만 존재하는 것이 아니다.
위상 정렬의 조건만 만족하면 모두 위상 정렬이 될 수 있다.

왜 DAG에 대해서만 실행할 수 있을까?

아침 일과를 짤 때 아침 운동을 하기 전에 양치를 하기로 했다고 해보자.
그리고 양치를 하기 전에 아침 운동을 하기로 했다고 해보자.
즉, 아침 운동과 양치 사이에 사이클이 있는 것이다.
이때 아침 일과의 순서를 정할 수 있을까?
불가능하다. 아침 운동을 하기 전에 양치를 해야하는데
양치를 하려면 아침 운동을 해야 한다.
즉, 모순이다.
이처럼 cycle이 존재할 때 위상 정렬을 하게 되면 u 이후에 v가 오는 동시에 v 이후에 u가 와야 한다.
그렇기 때문에 위상 정렬은 loop가 없는 그래프에 한해서만 실행할 수 있다.

위상 정렬의 구현

DFS와 stack을 이용해서 구현한다.
DFS(Depth First Search)를 이용하면 그래프의 가장 깊은 곳 먼저 탐색한다.
그리고 가장 깊은 곳부터 노드의 key를 차례대로 stack에 담는다.
그리고 모든 노드를 탐색한 후 stack에서 하나씩 꺼내서 차례대로 vector에 push 하면 위상 정렬이 끝난다.

void topoSortNode(vector<int> adj[], int key, stack<int>& ret) {
	if(visited[key] == true) {
    		return ;
        }
        visited[key] = true;
        for(int i = 0; i < adj[key].size(); i++) {
        	topoSortNode(adj, adj[key][i], ret);
        }
        ret.push(key); 
}

위상 정렬을 이용한 DAG 판정법

위상 정렬 알고리즘을 cyclic 그래프에 대해 실행한다고 가정해보자.
그럼 반드시 cycle의 진입점이 있을 것이다.
그 노드를 a라고 하자.
a에서 DFS를 실행하면 재귀 호출은 다시 a를 만나게 된다.
즉, 다시 topoSortNode(a)를 호출하게 된다.
a가 두번째 호출되었을 때는 visited[a] == true이지만 아직 a가 stack에 push되어 있지는 않다.
왜냐면 재귀호출이 끝나고 나서야 자신을 stack에 push하기 때문이다.
고로 a는 마지막에 push 된다.
이말은즉슨, topoSortNode(a)가 호출되었을 때 visited[a] == true이지만 stack에 아직 없다면 a에 대한 재귀 호출이 아직 안 끝났다는 것을 의미하고 곧, topoSortNode(a)에서 topoSortNode(a)를 호출했다는 의미가 된다.
a의 호출 과정이 끝났다면 a는 반드시 stack에 있어야 한다.
이 점을 이용해서 코딩을 이용하면 된다.
노드의 stack 존재 여부는 sorted라는 벡터를 통해서 저장했다.

bool judgeAcyclic(int key) {
    if(visited[key] == true) {
        if(sorted[key] == true) {
            return true;
        }
        return false;
    }
    visited[key] = true;
    for(auto i = 0; i < graph[key].size(); i++) {
        if(judgeAcyclic(graph[key][i]) == false) {
	        return false;
        }
    }
    sorted[key] = true;
    return true;
}

느낀 점

이 문제는 cycle이 존재한다는 것이 어떤 의미인지를 파악하는 게 중요한 문제였다.
우리 모두 앞으로 문제를 정확히 이해하는 습관을 갖도록 하자.