C++로 해결하는 중복 연결(Redundant Connection) 문제

문제 설명

루트가 없는 트리(unrooted tree), 즉 사이클이 존재하지 않는 무방향 그래프가 하나 있다고 가정해 보겠습니다. 입력으로 주어지는 그래프는 노드 값이 1부터 N까지 서로 겹치지 않는 N개의 노드로 이루어진 트리에 간선을 하나 더 추가한 형태입니다. 새로 추가된 간선은 1부터 N 사이에서 서로 다른 두 정점으로 구성되며, 기존에 존재하지 않던 간선이라는 점이 보장됩니다.

최종 그래프는 2차원 배열 edges로 표현됩니다. 각 원소는 [u, v] 형태의 쌍(u < v)이며, 노드 u와 v를 잇는 무방향 간선을 의미합니다.

목표는 간선 하나를 제거했을 때 남은 그래프가 정확히 N개의 노드를 가진 트리가 되도록 만드는 간선을 찾는 것입니다. 정답이 여러 개일 수 있으므로, 입력 배열에서 가장 마지막에 등장하는 간선을 답으로 반환해야 하며, 결과 역시 [u, v](u < v) 형식을 따라야 합니다.

예를 들어 입력이 [[1,2], [2,3], [3,4], [1,4], [1,5]]라면,

C++로 해결하는 중복 연결(Redundant Connection) 문제 – 유니온-파인드 활용법

출력은 [1,4]가 됩니다. 1과 4를 잇는 간선이 1 → 2 → 3 → 4 → 1로 이어지는 사이클을 완성하는 간선이기 때문입니다.

접근 방법: 유니온-파인드(Union-Find)

이 문제는 서로소 집합(Disjoint Set) 자료구조, 흔히 유니온-파인드라고 불리는 기법으로 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

간선을 입력 순서대로 하나씩 확인하면서, 해당 간선이 연결하는 두 정점이 이미 같은 집합(연결 요소)에 속해 있는지 검사합니다.
두 정점이 이미 연결되어 있다면 이 간선을 추가하는 순간 사이클이 생긴다는 뜻이므로, 이 간선이 곧 제거 대상(중복 간선)입니다.
배열을 끝까지 순회하며 조건을 만족하는 간선을 계속 갱신하면 자연스럽게 "마지막에 등장하는" 정답을 얻을 수 있습니다.

getParent() 함수 – 루트 찾기와 경로 압축

각 노드의 부모 정보를 저장하는 parent 배열을 사용합니다. 어떤 노드의 부모가 -1이면 그 노드가 집합의 루트입니다. 재귀적으로 부모를 따라 올라가 루트를 찾으면서, 찾은 루트를 경로상의 모든 노드에 기록하는 경로 압축(path compression)을 적용해 이후 탐색 속도를 크게 높입니다.

unionn() 함수 – 두 집합 합치기

두 정점 a, b의 루트(pa, pb)를 구한 뒤 다음을 수행합니다.

pa == pb라면 두 정점은 이미 같은 집합에 속해 있으므로 false를 반환합니다(사이클 감지).
그렇지 않으면 rank(집합의 크기)를 비교해 작은 쪽을 큰 쪽 아래로 붙여 트리의 균형을 유지합니다(크기 기반 합병).
합치기에 성공하면 true를 반환합니다.

전체 알고리즘 흐름

N := 1000으로 상수를 정의하고, 크기 N+5의 parent 배열과 rank 배열을 준비합니다.
입력된 모든 간선의 양 끝 정점에 대해 parent를 -1(자기 자신이 루트), rank를 1로 초기화합니다.
정답을 저장할 배열 ans를 선언합니다.
간선을 처음부터 끝까지 순회하며 u := edges[i][0], v := edges[i][1]을 꺼냅니다.
unionn(u, v)가 false를 반환하면(두 정점이 이미 연결되어 있으면) ans := edges[i]로 갱신합니다.
순회가 끝나면 ans를 반환합니다.

경로 압축과 크기 기반 합병을 함께 사용하면 시간 복잡도가 거의 선형인 O(N·α(N)) 수준으로 줄어듭니다(α는 아커만 함수의 역함수로, 실질적으로 상수로 취급됩니다). 따라서 노드 수가 많은 그래프에서도 매우 빠르게 동작합니다.

C++ 구현 예시

아래 코드를 통해 실제 구현을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v){
    cout << "[";
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

const int N = 1000;

class Solution {
public:
    int parent[N + 5];
    int rank_[N + 5];

    int getParent(int n){
        if (parent[n] == -1)
            return n;
        return parent[n] = getParent(parent[n]);
    }

    bool unionn(int a, int b){
        int pa = getParent(a);
        int pb = getParent(b);
        if (pa == pb)
            return false;
        if (rank_[pa] > rank_[pb]) {
            rank_[pa] += rank_[pb];
            parent[pb] = pa;
        }
        else {
            rank_[pb] += rank_[pa];
            parent[pa] = pb;
        }
        return true;
    }

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        for (int i = 0; i < n; i++) {
            parent[edges[i][0]] = parent[edges[i][1]] = -1;
            rank_[edges[i][0]] = rank_[edges[i][1]] = 1;
        }
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            if (!unionn(u, v)) {
                ans = edges[i];
            }
        }
        return ans;
    }
};

main(){
    Solution ob;
    vector<vector<int>> v = {{1,2}, {2,3}, {3,4}, {1,4}, {1,5}};
    print_vector(ob.findRedundantConnection(v));
}

참고로 using namespace std; 환경에서는 std::rank와 이름이 충돌할 수 있으므로, 위 코드에서는 배열 이름을 rank_로 사용했습니다.

실행 결과

입력

{{1,2}, {2,3}, {3,4}, {1,4}, {1,5}}

출력

[1, 4]

1과 4를 연결하는 간선이 순회 과정에서 마지막으로 발견된 중복 간선이므로, 최종 정답은 [1, 4]입니다.