1에서 N까지 번호가 매겨진 N개의 도시가 있다고 가정합니다. 연결이 있고 각 연결 [i]는 [city1, city2, cost]이며 이는 city1과 city2를 함께 연결하는 비용을 나타냅니다. . 모든 도시 쌍에 대해 두 도시를 함께 연결하는 연결 경로(길이 1일 수 있음)가 존재하도록 최소 비용을 찾아야 합니다. 비용은 사용된 연결 비용의 합계입니다. 작업이 불가능한 경우 -1을 반환합니다.
따라서 그래프가 다음과 같으면 -
그러면 출력은 6이 됩니다. 두 도시를 선택하면 모든 도시가 연결되므로 최소 2, [1, 5]
를 선택합니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
find()라는 메서드를 정의하면 x
가 걸립니다. -
부모[x]가 -1이면 x
를 반환합니다. -
부모[x] :=찾기(부모[x])
-
부모 반환[x]
-
Union()이라는 다른 메서드를 만듭니다. x와 y가 필요합니다.
-
parent_x :=찾기(x), parent_y :=찾기(y)
-
parent_x =parent_y이면 반환, 그렇지 않으면 parent[parent_y] :=parent_x
-
기본 방법에서 n과 conn이 필요합니다.
-
parent :=크기가 n인 배열을 - 1로 채우고 disjoint로 설정 :=n - 1, 비용 :=0
-
c :=conn의 정렬된 목록, 비용을 기준으로 정렬
-
나는 :=0
-
i
-
x :=c[i, 0] 및 y :=c[i, 1]
-
find(x)가 find(y)와 같지 않으면 disjoint를 1만큼 줄이고 비용을 c[i, 2]만큼 늘리고 Union(x, y)을 수행합니다.
-
i를 1 증가
-
-
disjoint가 0일 때 비용을 반환하고, 그렇지 않으면 -1을 반환합니다.
예제(파이썬)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
class Solution(object): def find(self, x): if self.parent[x] == -1: return x self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self,x,y): parent_x = self.find(x) parent_y = self.find(y) if parent_x == parent_y: return self.parent[parent_y] = parent_x def minimumCost(self, n, connections): self.parent = [ -1 for i in range(n+1)] disjoint = n-1 cost = 0 c = sorted(connections,key=lambda v:v[2]) i = 0 while i<len(c) and disjoint: x = c[i][0] y = c[i][1] if self.find(x)!=self.find(y): disjoint-=1 cost+=c[i][2] self.union(x,y) i+=1 return cost if not disjoint else -1 ob = Solution() print(ob.minimumCost(3, [[1,2,5], [1,3,6], [2,3,1]]))
입력
3 [[1,2,5],[1,3,6],[2,3,1]]
출력
-1