LV 3: 네트워크

문제 링크

LV 3: 네트워크

구현 방식

• 무난한 find-union 문제이다
• 주의해야할 점: union을 수행한다고해서, 항상 모든 parent에 항상 가장 작은 부모노드가 저장되는 것은 아님
  • 더 큰 부모에 작은 부모가 할당되었으니 작은 노드쪽으로 union이 수행된 건 맞으나, find()를 한 번 더 하지 않는다면, 최상단 노드만 갱신되기 때문에 하위 노드들은 아직 union 수행 전의 노드가 최상단 부모 노드라고 기억하게 됨
  • 따라서, 마지막에 find 연산을 쭉 수행해주어야함

코드

def solution(n, computers):
    
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    def union(a, b):
        a = find(a); b = find(b)
        if a < b: parent[b] = a
        else: parent[a] = b
        
    parent = [_ for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if computers[i][j] == 1:
                if find(i) != find(j): union(i, j)
    
    for i in range(n): find(i) # parent 한 번 갱신 해줘야함
    
    return len(set(parent))