문제 설명
루트가 있는 트리(rooted tree)란 방향 그래프의 한 종류로, 다른 모든 노드가 이 노드의 자손이 되는 단 하나의 노드(루트)가 존재하고, 루트를 제외한 모든 노드는 정확히 하나의 부모를 가지며, 루트 자신은 부모가 없는 그래프를 의미합니다.
입력으로 주어지는 그래프는 N개의 노드(모든 값은 고유함)로 구성된 루트 트리에서 시작해 하나의 추가 방향 간선이 덧붙여진 형태입니다. 추가된 간선은 1부터 N 사이의 서로 다른 두 정점을 선택하며, 기존에 존재하지 않던 새로운 간선입니다.
그래프는 간선 목록을 담은 2차원 배열로 표현됩니다. edges의 각 원소는 [u, v] 형태의 쌍으로, 노드 u와 v를 연결하는 방향 간선을 나타내며 이때 u는 v의 부모 노드입니다.
목표는 제거했을 때 결과 그래프가 N개의 노드를 가진 루트 트리가 되도록 만드는 간선을 찾는 것입니다. 정답이 여러 개일 수 있으므로, 주어진 2차원 배열에서 마지막에 등장하는 답을 반환해야 합니다.
입력 예시
예를 들어 입력이 아래와 같다면,
출력은 [2,3]이 됩니다.
풀이 접근 방법
이 문제는 유니온-파인드(Union-Find, 서로소 집합) 자료구조를 활용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 '부모가 두 개인 노드'의 존재 여부와 '사이클'의 발생 여부를 동시에 추적하는 것입니다. 단계별로 살펴보겠습니다.
- getParent() 함수를 정의합니다. 이 함수는 노드와 parent 배열을 인자로 받습니다.
- parent[node]가 -1이면 node를 그대로 반환합니다.
- 그렇지 않으면 parent[node] = getParent(parent[node], parent)를 통해 경로 압축을 수행하면서 최상위 조상을 반환합니다.
- 메인 메서드에서는 다음 과정을 수행합니다.
- n := edges의 크기
- 크기가 n + 5인 parent 배열을 정의하고 모든 값을 -1로 초기화합니다.
- 크기가 n + 5인 ds 배열을 정의하고 모든 값을 -1로 초기화합니다.
- last := -1, second := -1, first := -1로 초기화합니다.
- i := 0부터 i < n까지 반복하며 다음을 수행합니다.
- u := edges[i][0], v := edges[i][1]
- 만약 parent[v]가 -1이 아니라면(v에 이미 부모가 존재한다면), first := parent[v], second := i로 설정하고 다음 반복으로 넘어갑니다.
- parent[v] := i로 설정한 뒤, parentU := getParent(u, ds), parentV := getParent(v, ds)를 계산합니다.
- parentU와 parentV가 같다면 사이클이 발생한 것이므로 last := i로 기록합니다.
- 그렇지 않다면 ds[parentV] := parentU로 두 집합을 병합합니다.
반복이 끝난 후 결과는 세 가지 경우로 나뉩니다.
- last가 -1이라면(사이클은 없고 부모가 두 개인 노드만 존재), edges[second]를 반환합니다.
- second가 -1이라면(사이클만 존재하고 부모가 두 개인 노드는 없음), edges[last]를 반환합니다.
- 두 경우가 모두 존재한다면, edges[first]를 반환합니다.
아래 구현을 통해 더 자세히 이해해 보겠습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
int getParent(int node, vector <int>& parent){
if(parent[node] == -1)return node;
return parent[node] = getParent(parent[node], parent);
}
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
int n = edges.size();
vector <int> parent(n + 5, -1);
vector <int> ds(n + 5, -1);
int last = -1, second = -1, first = -1;
int u, v;
int parentU, parentV;
for(int i = 0; i < n; i++){
u = edges[i][0];
v = edges[i][1];
if(parent[v] != -1){
first = parent[v];
second = i;
continue;
}
parent[v] = i;
parentU = getParent(u, ds);
parentV = getParent(v, ds);
if(parentU == parentV){
last = i;
}else ds[parentV] = parentU;
}
if(last == -1)return edges[second];
if(second == -1)return edges[last];
return edges[first];
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,2},{1,3},{2,3}};
print_vector(ob.findRedundantDirectedConnection(v));
}
입력
{{1,2},{1,3},{2,3}}출력
[2, 3]