[릿코드 1319] Number of Operations to Make Network Connected(파이썬/python)

https://leetcode.com/problems/number-of-operations-to-make-network-connected/description/

Number of Operations to Make Network Connected - LeetCode

 

연결된 노드의 모음을 다루는 문제여서 유니온 파인드 알고리즘을 사용했다..

 

수행시간이 무지 느리네 ㅠ

 

from typing import List


class Solution:
    def __init__(self):
        self.parent = []

    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        self.parent = [i for i in range(n)]
        connections_cnt = len(connections)
        # 일단 서로 연결된 노드끼리 연결해준다.
        for node_x, node_y in connections:
            self.merge(node_x, node_y)

        print(self.parent)
        # 최상위 부모를 다시 재연결해줌
        for node in range(n):
            self.find(node)

        # 연결된 노드의 그룹을 찾아준다.
        parent_set = set(self.parent)
        for p in parent_set:
            cnt = self.parent.count(p)
            connections_cnt -= cnt - 1

        # 만약 사용할 수 있는 커넥션이 노드그룹 갯수 -1 (서로 연결을하니) 보다 크면 리턴
        if connections_cnt >= len(parent_set) - 1:
            return len(parent_set) - 1
        else:
            return -1

    def find(self, node: int) -> int:
        if self.parent[node] == node:
            return node

        self.parent[node] = self.find(self.parent[node])
        return self.parent[node]

    def merge(self, node_x: int, node_y: int):
        node_x = self.find(node_x)
        node_y = self.find(node_y)

        if node_x == node_y:
            return

        self.parent[node_x] = node_y