유니온파인드3 [leetcode] 684. Redundant Connection 문제 : https://leetcode.com/problems/redundant-connection/ n개의 노드와 n개의 간선으로 이루어진 무방향 그래프가 주어질 때, n개의 노드로 이루어진 트리가 될 수 있도록 제거해야 하는 간선을 구하여라. 조건에 그래프들은 연결되어 있고 노드가 n개인데 간선도 n개라고 하니, 트리의 특징 중 하나인 간선의 개수는 정점 개수 - 1 이다.를 생각하면 정답이 되는 간선은 1개가 나올 수 있고. 이 간선은 사이클을 만듬을 알아낼 수 있다. 크루스칼 알고리즘 구현에서 사이클이 생성됨을 알아내기 위해 유니온 파인드를 사용했었다. 이를 응용하여, 입력으로 주어지는 간선들을 Union-Find 의 Union 연산으로 하나의 집합으로 합치면서 이미 같은 집합인데 Union 연산.. 2021. 6. 26. 유니온 파인드(Union-Find) 유니온 파인드(Union-Find)는 집합을 표현하기 위한 자료구조입니다. 이를 표현하기 위해 트리에서 부모노드를 저장하는 배열을 만듭니다. 부모노드가 없는 루트노드인 경우는 자기자신을 저장합니다. 이때 최상위 부모노드가 같은 값들이 같은 집합에 속하게 됩니다. [그림 1]에서는 1, 2, 3이 같은 집합. 4, 5가 같은 집합입니다. 주의할 점은, 부모노드가 아닌 최상위 부모노드가 같은 노드들이 같은 집합에 속합니다. [그림 2]에서 노드 4와 노드 2는 모두 같은 집합에 속하지만 부모노드 배열만 봐서는 같은 집합에 속하는지 알 수 없습니다. 같은 집합에 속하는지 알기 위해서는 각 노드들의 최상위 부모노드 배열을 알아야 합니다. 노드 4의 부모노드는 3이지만 최상위부모노드는 1이 됩니다. 다른 노드들의.. 2021. 6. 26. [Programmers] 섬 연결하기 문제 : https://programmers.co.kr/learn/courses/30/lessons/42861 오랜만에 푸는 최소신장트리문제~ 크루스칼 알고리즘으로 풀었다. 먼저 cost 오름차순으로 costs 배열을 정렬한다. costs 배열을 탐색하면서 Union-Find로 해당 간선을 연결하면 사이클이 생기는지 확인한다. 만일 두 정점의 부모노드가 같다면 연결하면 사이클이 생기기 때문에 해당 간선을 선택하지 않는다. 두 정점의 부모노드가 다르면 해당 간선을 연결해도 사이클이 생기지 않기 때문에 해당 간선을 선택하고 해당 간선의 비용을 정답에 더해준다. 시간복잡도는 간선들을 오름차순 정렬하는데 드는 시간인 O(ElogE) 소스코드 : https://github.com/fpdjsns/Algorithm/.. 2021. 6. 14. 이전 1 다음
