[DFS,UnionFind] 네트워크 - 프로그래머스

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

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

Fact Finding

---

• Disjoint Set을 찾는 문제

Algorithm Flow

---

• Union Find(union by Rank) 알고리즘을 사용하여 Disjoint Set을 나눔

Disjoint Set을 찾는 알고리즘인 Union Find에 대해서는 추후 포스팅에서 자세하게 다루겠습니다!

( 양이 너무 많아질 거 같아서 ㅠㅠ)

즉, 서로소인 partition을 찾는데 최적화된 알고리즘이라는 것만 언급하겠습니다

 

Union Find는 다음과 같은 코드로 동작을 수행합니다. 크게

- MakeSet(v)

- Union(u,v)

- Find(v)

로 구성됩니다.

 

def Find(v, parent) : 
    if parent[v] != v :
        parent[v] = Find(parent[v], parent)
    return parent[v]
def Union(x, y, parent, rank) : 
    if rank[x] > rank[y] : 
        parent[y] = x
    elif rank[x] < rank[y] : 
        parent[x] = y
    else : 
        parent[y] = x
        rank[x] += 1
    return parent, rank
parent = {}
rank = {}
# Make set
for i in range(n) :
    parent[i] = i
    rank[i] = 0

 

 

Union Find 알고리즘을 사용하여 문제를 푼 코드는 다음과 같다. 

 

구현 코드

# 반례 
def Find(v, parent) : 
    if parent[v] != v :
        parent[v] = Find(parent[v], parent)
    return parent[v]
def Union(x, y, parent, rank) : 
    if rank[x] > rank[y] : 
        parent[y] = x
    elif rank[x] < rank[y] : 
        parent[x] = y
    else : 
        parent[y] = x
        rank[x] += 1
    return parent, rank
def solution(n, computers):
    parent = {}
    rank = {}
    # Make set
    for i in range(n) :
        parent[i] = i
        rank[i] = 0
    ## computers[i].index(edge) ---- 고유 인덱스가 저장이 되지 않는다!!!
    for i in range(len(computers)) : 
        for edge in range(len(computers[i])) : 
            if computers[i][edge] == 1 and edge != i : 
                v1 = i
                v2 = edge
                x = Find(v1, parent)
                y = Find(v2, parent)
                if x != y :
                    parent, rank = Union(x, y, parent, rank)
    for i in range(n) : 
        root = Find(i, parent)
        parent[i] = root
    value = []
    value = list(parent.values())
    value_set = len(set(value))
    
    return value_set

Time Complexity

---

n^2 * G(n) 일거 같다!

n^2 —> 이중 for문

G(n) → union by rank 시간 복잡도