위상 정렬을 위한 Kahn 알고리즘

[https://school.programmers.co.kr/learn/courses/30/lessons/76503]

최하위 노드(리프)에서 부터 루트까지 값을 전달해야 하는 문제였습니다. 저는 이 문제를 해결하기 위해 트리를 만들고 DFS로 값을 누적하는 방식을 사용했습니다.

DFS로 순회해도 각 노드를 1회만 방문하기 때문에 O(N)안에 모든 데이터를 순회할 수 있었고, 제한 시간 내에 통과하여 정답 판정을 받았습니다. (최대 100ms 미만)

하지만, 데이터가 지금 보다 더 많으면서 일렬로 늘어선 트리가 입력에 들어 있었다면 오버플로우 될 수도 있겠다는 생각이 들었습니다. 오버헤드도 고려해야 하구요.

위상 정렬을 위한 Kahn Algorithm

위상 정렬이란 DAG(Directed Acyclic Graph, 비순환 방향 그래프)에서 선행 관계를 만족하도록 정점을 나열하는 것입니다. 그 중에서 Kahn은 indegree(진입차수, 자신을 가리키는 화살표의 개수)를 사용하여 정렬합니다.

핵심은 indegree가 0인 정점부터 제거하는 것입니다. 트리에서는 리프 노드가 이에 해당합니다. indegree = 0인 노드를 큐에 추가하여 명령을 처리하고 그래프에서 제거하는 것을 반복합니다. 노드가 제거되면서 연결된 indegree가 감소하여 자연스럽게 부모였던 노드가 리프가 되는 시점을 알아낼 수 있습니다. 아주 간단하네요.

또한, 트리가 아니어도 사용할 수 있습니다. (루트 또는 부모가 여러 개)

적용해서 풀어보기

그래프를 생성할 때 indegree를 추가로 기록합니다.

    for(const auto& e: edges)
    {
        graph[e[0]].push_back(e[1]);
        graph[e[1]].push_back(e[0]);
        degree[e[0]]++;
        degree[e[1]]++;
    }

진입 차수가 1인 노드를 대기열에 추가합니다. 원래는 진입 차수가 0인 노드를 추가해야 하지만 해당 문제의 입력으로는 방향을 알 수 없기 때문에 양방향 그래프로 먼저 만들고 진입 차수가 1일 경우에 리프로 판단합니다. 전처리하면 단방향으로도 만들 수 있지만 정렬 과정을 추가하며 얻는 이득이 적으므로 수행하지 않았습니다.

양방향(무방향) 그래프이기 때문에 degree로 표현해야 하지만 혼용해서 사용합니다.

    queue<long long> q;
    for(int i = 0; i < degree.size(); ++i)
    {
        if(degree[i] == 1) q.push(i);
    }

리프 노드는 연결된 노드가 부모 노드밖에 없으므로 연결된 노드에 자신의 값을 추가합니다. 값을 처리하고 indegree를 감소시키다 보면 부모 노드의 indegree도 1이 되는데, 이때 1이 된 노드를 다시 대기열에 추가하는 동작을 반복하면 정답을 도출할 수 있습니다.

    long long answer = 0;
    vector<bool> visit(n);
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        
        answer += abs(weights[cur]);
        visit[cur] = true;
        
        for(const auto& g: graph[cur])
        {
            if(!visit[g])
            {
                weights[g] += weights[cur];
                --degree[cur];
                --degree[g];

                if(degree[g] == 1) q.push(g);
            }
        }
    }

    return answer;