Lee 코딩 Lee 코딩

문제 설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 ((n-1) * n) / 2이하입니다. 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다..

= Disjoint-Set 서로소 집합 알고리즘이라고도 불림. 그래프에서 여러 개의 노드 중 두 개의 노드를 선택해서 이 노드들이 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. - find : 노드의 부모가 같은지 확인하여 현재 같은 집합에 속하는지 확인하는 것 - union : 두 노드가 각각 포함되어 있는 집합을 합치는 것 1. 처음에 모든 노드들이 연결되어 있지 않을 때 -> 자기 자신이 부모 i 0 1 2 3 4 5 parent[i] 0 1 2 3 4 5 2. 1과 3, 2와 5가 각각 연결되어 있을 때 i 0 1 2 3 4 5 parent[i] 0 1 2 1 4 2 1과 3의 부모를 합쳐주고, 2와 5의 부모를 합쳐 준다(Union) 이 때는 더 작은 값으로 합쳐준다 3. 1-2-3처럼 연..