백준 9470 - Strahler 순서

이번 문제는 백준 골드 3 Strahler 순서 문제이다.
문제 이름이 엄청 특이한데, 실제로 사용되는 개념이라고 한다.
문제를 한 번 차근차근 이해해보자.

강의 근원으로부터 물이 흘러 내려오는데, 각 정점에 값이 매겨진다.
이전 정점에 매겨진 값에 따라 현재 정점의 값이 정해지는데,
이전 정점이 하나라면 그 값을 그대로 물려받는다.
여러개라면, 그 중 가장 큰 값을 그대로 물려받는다.
만약 큰 값이 여러개라면, 가장 큰 값 + 1을 물려받게 된다.

노드는 최대 1000개 까지 입력으로 주어진다.
주어지는 노드의 수는 그렇게 많지 않은 것 같다.
과연 어떻게 각 정점들을 모두 훑으며 값을 매길 수 있을까?
우선은 그래프이기 때문에, 가장 먼저 떠오르는 것은 BFS, DFS이다.

하지만 부모 정점의 모두의 값에 따라 현재 노드가 결정되기 때문에,
DFS를 사용하기엔 힘들 것 같으니 우선 BFS로 한 번 생각해보자.

BFS?

BFS를 이용해서 그래프를 옆으로 훑도록 한다.
대신 부모 정점에서 자식 정점으로 내려갈 때 값을 부여하며 내려가보자.

처음 간선 입력을 받을 때, 도착지에 없는 정점들은 강의 근원이 된다.
강의 근원을 찾아 1점을 먼저 부여한 다음 아래로 탐색을 진행해보자.
만약 자식 정점이 0점이라면, 자신의 점수를 일단 그냥 부여하도록 하고,
0이 아니라면, 자식 정점에 저장된 값과 자신의 값 중 더 큰 값을 부여한다.

근데 이 부분에서 지금 논리는 문제가 발생한다.
가장 큰 값인 부모 정점이 여러개면, 가장 큰 값 + 1을 자식 노드에 저장하는데,
해당 로직은 그 때 그 때 저장을 하는 방법으로는 구현 방법이 생각나지 않는다.
가장 큰 값이 무엇인지 먼저 찾아야 하기 때문에, 최소 두 번은 돌아야 한다.

위상 정렬!

골머리를 앓다가 결국 다른 사람들의 풀이를 보기로 했다…
사실 이 문제를 푸는 확실한 정답은 위상 정렬이라고 한다.

위상 정렬을 통해서 각 정점을 시작점부터 순서대로 방문한다.
단, 부모 정점을 저장하며 나아가서 부모 정점 점수의 최대 값을 저장한다.
그래야 자식 정점의 점수를 조건에 맞게 계산할 수가 있다.
자식 정점의 점수 계산 부분이 가장 머리 아팠던 부분인데, 해결이 됐다.

위상 정렬을 사용할 수 있는 이유는, 사이클이 없는 유향 그래프이기 때문이다.
가장 처음 방문해야 하는 진입 차수가 0인 정점들은 강의 근원이다.
강의 근원들에게 모두 1점을 부여하고 탐색을 시작하도록 한다.

for (int i = 1; i <= vertex; i++) {
        if (indegree[i] == 0) {
            topology_q.push(i);
            strahler[i] = 1;
        }
    }

강의 근원에 연결된 정점들의 진입 차수를 하나씩 줄이며 탐색을 진행한다.
이 때 핵심은, 진입 차수가 줄어드는 정점의 부모를 기억해야 한다는 것이다.

for (int i = 0; i < graph[curr_node].size(); i++) {
     int next_node = graph[curr_node][i];
     indegree[next_node]--;
     cache[next_node].push_back(strahler[curr_node]);

그래야 최대 값을 구하고, 현재 정점의 값을 매겨줄 수가 있다.
핵심 로직의 전체 구현코드는 아래와 같다.

void calculate_strahler() {
    queue<int> topology_q;
    vector<int> cache[1001];
    for (int i = 1; i <= vertex; i++) {
        if (indegree[i] == 0) {
            topology_q.push(i);
            strahler[i] = 1;
            // 진입차수가 0이면 강의 근원이라는 말이다.
        }
    }

    while (!topology_q.empty()) {
        int curr_node = topology_q.front();
        topology_q.pop();

        for (int i = 0; i < graph[curr_node].size(); i++) {
            int next_node = graph[curr_node][i];
            indegree[next_node]--;
            // 탐색을 한 번 했으니 진입 차수 감소
            cache[next_node].push_back(strahler[curr_node]);

            if (indegree[next_node] == 0) {
                topology_q.push(next_node);
                // 진입 차수가 0인 노드가 생기면 큐에 삽입
                int max_strahler = 0;
                for (int i = 0; i < cache[next_node].size(); i++)
                    max_strahler = max(max_strahler, cache[next_node][i]);
                // 노드에 연결되어있던 이전 노드의 strahler 중 최대 값

                int check_strahler = 0;
                for (int i = 0; i < cache[next_node].size(); i++)
                    if (cache[next_node][i] == max_strahler)
                        check_strahler++;

                if (check_strahler > 1)
                    strahler[next_node] = max_strahler + 1;
                else
                    strahler[next_node] = max_strahler;
            }
        }
    }
}