최근 두 가지 그래프 관련 문제를 접하게 되었는데, 각각 복잡한 구조를 다루는 데 있어 유사한 접근 방식을 사용하고 있어 정리해보았다.

AcWing 2069. 네트워크 분석 태그: 병합-찾기 집합, 동적 연결성 관리

이 문제는 초기에 간선이 없는 (n)개의 노드로 구성된 네트워크에서 시작한다. 두 가지 유형의 연산이 주어진다:

1. 두 노드 (a)와 (b)를 연결한다.
2. 노드 (p)에 값 (t)를 추가하고, 이 값은 연결된 모든 인접 노드 및 하위 노드로 전파된다.

최종적으로 각 노드의 누적 값을 출력해야 한다. 이를 위해 유니온-파인드(Union-Find) 자료구조를 활용하여 연결 요소를 관리하며, 각 컴포넌트의 총값과 크기를 추적한다.

#include <iostream>
#include <cstring>

using namespace std;

const int MAXN = 110010;

int parent[MAXN];
int value[MAXN];

int find(int x) {
    if (parent[x] != x) {
        int root = find(parent[x]);
        value[x] += value[parent[x]];
        parent[x] = root;
    }
    return parent[x];
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
        value[i] = 0;
    }

    int operation_count = n;
    while (m--) {
        int op, a, b;
        scanf("%d %d %d", &op, &a, &b);
        if (op == 1) {
            int root_a = find(a);
            int root_b = find(b);
            if (root_a != root_b) {
                parent[root_a] = root_b;
                value[root_a] += value[root_b];
                // 새로운 노드로 확장
                operation_count++;
                parent[operation_count] = operation_count;
                value[operation_count] = 0;
            }
        } else {
            int root = find(a);
            value[root] += b;
        }
    }

    for (int i = 1; i <= n; ++i) {
        int root = find(i);
        printf("%d ", value[i] + value[root]);
    }

    return 0;
}

이 코드는 트리 구조의 합산을 효율적으로 처리하기 위해 경로 압축과 함께 값 누적을 저장하는 기법을 사용한다.

LeetCode 2192. DAG에서 특정 노드의 모든 조상 찾기 태그: 위상 정렬, 너비 우선 탐색, 인접 리스트

주어진 방향성 비순환 그래프(DAG)에서 각 노드의 모든 조상을 찾아야 한다. 조상은 해당 노드로 도달할 수 있는 모든 선행 노드들이다.

해결 방법은 다음과 같다:

• 인접 리스트와 진입 차수 배열을 준비한다.
• 진입 차수가 0인 노드부터 시작해 너비 우선 탐색(BFS)으로 위상 순서를 확보한다.
• 각 노드가 처리될 때, 다음 노드에 현재 노드와 그 모든 조상 정보를 병합한다.

class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<unordered_set<int>> ancestors(n);
        vector<vector<int>> graph(n);
        vector<int> inDegree(n, 0);

        for (const auto& edge : edges) {
            int from = edge[0], to = edge[1];
            graph[from].push_back(to);
            inDegree[to]++;
        }

        queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (int v : graph[u]) {
                ancestors[v].insert(u);
                for (int anc : ancestors[u]) {
                    ancestors[v].insert(anc);
                }
                if (--inDegree[v] == 0) {
                    q.push(v);
                }
            }
        }

        vector<vector<int>> result(n);
        for (int i = 0; i < n; ++i) {
            result[i] = vector<int>(ancestors[i].begin(), ancestors[i].end());
            sort(result[i].begin(), result[i].end());
        }

        return result;
    }
};

여기서 중요한 점은 조상 정보를 순차적으로 확장하면서 중복 제거하는 것이다. unordered_set을 사용해 중복을 방지하고, 최종 결과는 정렬되어 반환된다.

두 문제 모두 그래프의 구조적 특성을 활용하여 효율적인 해결을 가능하게 한다. 첫 번째는 동적 연결성 유지에 유니온-파인드를, 두 번째는 순서 기반 데이터 전파에 위상 정렬 + BFS를 적용했다. 이러한 기법들은 실전 문제 해결에서 매우 강력한 무기다.