level - medium
[문제 내용]
간략히 요약하자면,
주어진 edges를 이용해 cycle이 없이 연결되어 있는 tree를 만드는 것으로
주어진 edges 중에 삭제할 수 있는 것을 반환하되
여러개가 있으면 가장 마지막에 input으로 주어진 것을 반환하도록 하는 것이다.
[example 1]
input: edges = [[1,2], [1,3], [2,3]]
output: [2,3][example 2]
Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4][해결 방법]
edges를 차례로 연결하여 cluster를 구성하고
그 구성된 cluster내에서 edges가 존재할 시 삭제 하여도 되는 것으로 간주하였다.
class Solution {
public int[] findRedundantConnection(int[][] edges) {
int[] redundant = null;
ArrayList<HashSet<Integer>> clusters = new ArrayList<>();
for(int[] edge : edges) {
boolean noAdded = true; // cluster에 edge가 존재하는 지
boolean connect = false; // cluster가 연결되어 있는 지
HashSet<Integer> con1 = null, con2 = null; // 연결되어 있는 경우 cluster 정보
for(HashSet<Integer> cluster : clusters) {
if(cluster.contains(edge[0]) && cluster.contains(edge[1])) {
// 삭제해도 되는 경우
noAdded = false;
redundant = edge;
break;
} else if(cluster.contains(edge[0]) || cluster.contains(edge[1])){
// edge 를 이루는 점 중 하나만 가지고 있어 연결될 수 있는 경우
noAdded = false;
if(connect) {
con2 = cluster;
break;
} else {
con1 = cluster;
}
cluster.add(edge[0]);
cluster.add(edge[1]);
connect = true;
}
}
if(noAdded) {
// 어떤 cluster에도 속하지 않는 경우, 새롭게 추가
HashSet<Integer> cluster = new HashSet<>();
cluster.add(edge[0]);
cluster.add(edge[1]);
clusters.add(cluster);
}
if(con1 != null && con2 != null) {
// 두개의 cluster가 연결되어 있는 경우
con1.addAll(con2);
clusters.remove(con2);
}
}
return redundant;
}
}