프로그래머스 네트워크 python

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/43162?language=python3 

코딩테스트 연습 - 네트워크

 

2. 풀이

하나로 합쳐져있는 집합을 구하는 방법은 Union-Find이다.

 

 

3. 구현

def find(x, parent):
    if parent[x]==x:
        return x
    parent[x]=find(parent[x], parent)
    return parent[x]
        
    
def uni(x, y, parent):
    x = find(x, parent)
    y = find(y, parent)
    if x==y:
        return
    parent[x]=y
    return


def solution(n, computers):
    answer = 0
    # 빈배열 만들기
    parent = [i for i in range(n)]
    
    for i in range(n):
        for j in range(n):
            if computers[i][j]==1:
                uni(i,j,parent)
    # print(parent)
    
    for i in range(len(parent)):
        parent[i]=find(i, parent)
    
    answer = len(set(parent))
                
    return answer