위상 정렬

설명

위상 정렬(topological sort)는 순서가 정해진 원소를 정렬하는 알고리즘이다. 대학교 강의의 선수과목처럼 한 강의를 수강하기 전에 무조건 들어야 하는 강의가 있다면 그것을 고려해 강의 순서를 정렬하는 알고리즘이 바로 위상 정렬이다. 위상정렬은 DAG(Directed Acyclyc Graph, 방향성 비순환 그래프)에서만 가능하다.

선수과목을 그래프로 표현한 예로, 이런 경우 듣는 강의의 순서를 위상 정렬로 정렬할 수 있다(답이 하나는 아니다). 예를 들어 컴퓨터프로그래밍→객체지향프로그래밍→인터넷프로그래밍→컴퓨터시스템→디지털논리회로→운영체제→시스템프로그래밍 한 방법이 있을 수 있고, 컴퓨터프로그래밍→객체지향프로그래밍→인터넷프로그래밍→컴퓨터시스템→운영체제→디지털논리회로→시스템프로그래밍 이런 방법이 있을 수 있다.

구현

위상 정렬을 하는 방법은 두 가지가 있다. DFS를 활용하는 방법과 큐를 활용하는 방법이다. 아래 코드는 위 그래프를 인접 리스트로 구현한 것이며, 방법 1과 2를 사용하여 위상 정렬을 구현하는 법을 아래 기술한다.

//설명을 위해 string, unordered_map과 set으로 그래프와 방문 여부를 체크했지만, 보통 문제에서는
//노드가 정수 형태여서 int vector 또는 배열을 사용하여 체크하면 된다.
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    unordered_map<string, vector<string>> graph;
    graph["컴퓨터 프로그래밍"] = {"객체 지향 프로그래밍"};
    graph["객체 지향 프로그래밍"] = {"인터넷 프로그래밍", "컴퓨터시스템", "운영체제"};
    graph["컴퓨터시스템"] = {"디지털 논리회로"};
    graph["운영체제"] = {"시스템 프로그래밍"};
    topologicalSortWithDFS(graph);
    topologicalSortWithQueue(graph);
    return 0;
}

방법 1 - DFS

DFS를 활용하여 위상 정렬을 하는 법이 있다. DFS는 재귀적으로 해당 노드의 인접 노드들을 방문하여 모든 노드를 방문하는 방법인데, 이때 인접 노드를 모두 방문 후 해당 노드를 스택에 넣고, 마지막에 스택에서 모두 꺼내면 위상 정렬이 된다.

void dfs(unordered_map<string, vector<string>> &graph, unordered_set<string> &visited, stack<string> &stk, string node) {
    visited.insert(node);
    for (auto &next : graph[node]) {
        if (visited.find(next) == visited.end()) {
            dfs(graph, visited, stk, next);
        }
    }
    stk.push(node); //이곳에서 스택에 넣어준다. 더이상 인접한 노드가 없는 노드부터 스택에 쌓인다.
}

void topologicalSortWithDFS(unordered_map<string, vector<string>> &graph) {
    unordered_set<string> visited;
    stack<string> stk;
    for (auto it = graph.begin(); it != graph.end(); it++) {
        if (visited.find(it->first) == visited.end()) {
            dfs(graph, visited, stk, it->first);
        }
    }
    while (!stk.empty()) {
        cout << stk.top() << "\n";
        stk.pop();
    }
}

방법 2 - Queue

1. inDegree가 0인 노드들을 큐에 넣는다. inDegree란 노드로 들어오는 간선의 개수를 말한다.
2. 큐의 원소를 하나씩 pop하며 출력하고 인접한 노드의 inDegree를 1 감소한다.
3. 원소의 개수만큼 1→2를 반복한다.

void topologicalSortWithQueue(unordered_map<string, vector<string>> &graph) {
    queue<string> q;
    unordered_map<string, int> inDegree;
    //보통 문제에서 inDegree는 입력을 받을 때 개수를 세어준다.
    //들어오는 간선의 개수를 count하면 되지만 편의상 이곳에서는 미리 지정을 한다.
    inDegree["컴퓨터 프로그래밍"] = 0;
    inDegree["객체 지향 프로그래밍"] = inDegree["인터넷 프로그래밍"] = inDegree["컴퓨터시스템"]
        = inDegree["운영체제"] = inDegree["디지털 논리회로"] = inDegree["시스템 프로그래밍"] = 1;
    for (auto it = inDegree.begin(); it != inDegree.end(); it++) {
        if (it->second == 0) {
            //inDegree가 0인 노드를 큐에 넣는다.
            q.push(it->first);
        }
    }
    for (int i = 0; i < 7; i++) { //그래프의 노드의 개수만큼 반복한다. 이또한 보통 문제에서 입력받지만 편의상 직접 넣는다.
        if (q.empty()) { //노드 개수만큼 반복 전에 큐가 빈다면 사이클이 있다는 것이다.
            cout << "사이클 존재";
            return;
        }
        string here = q.front();
        q.pop();
        cout << here << "\n";
        for (auto &next : graph[here]) {
            if (--inDegree[next] == 0) { //연결된 노드의 inDegree를 1 감소하고, 그것이 0이면 큐에 넣는다.
                q.push(next);
            }
        }
    }
}