프로그래머스: 네트워크

그래프의 서로소 판별 문제이다.

아래 알고리즘을 그대로 사용한다.

https://focalpoint.tistory.com/12

서로소 집합 알고리즘

def solution(n, computers):
    edges = []
    for i in range(n):
        for j in range(i+1, n):
            if computers[i][j] == 1:
                edges.append([i, j])
    
    parent = [0] * n
    for i in range(n):
        parent[i] = i
    
    def find_parent(parent, a):
        if parent[a] == a:
            return a
        parent[a] = find_parent(parent, parent[a])
        return parent[a]
    
    def union_parent(parent, a, b):
        a = find_parent(parent, a)
        b = find_parent(parent, b)
        if a < b:
            parent[b] = a
        else:
            parent[a] = b
    
    for edge in edges:
        u, v = edge
        union_parent(parent, u, v)
    
    for i in range(n):
        find_parent(parent, i)
        
    nets = set()
    for i in range(n):
        if parent[i] not in nets:
            nets.add(i)
    
    return len(nets)