BaekJoon 4195번 : 친구 네트워크 (python)

BaekJoon 4195번 : 친구 네트워크 (G2 26.552%)

친구 네트워크 문제

Union-Find 알고리즘 활용 문제이다.

• 해당 문제는 숫자를 이용한 노드 대신 실제로 나올 수 있는 환경인 문자열을 이용하게 된다. 해당 문자열을 숫자와 같이 변환하기 위해 dictionary를 사용해주었고 해당 문자열에 고유한 index값을 정의해준다.
• 해당 노드들을 고유한 값으로 변환해서 union하였을 때 해당 노드들의 root값이 통일되고 동시에 rank값 즉, 해당 집합의 크기를 작은쪽에서 큰쪽으로 합쳐주는 과정으로 변환해준다.

느낀점

기존의 효율성을 위해 사용했던 rank값을 조금 변환하여 집합의 크기로 생각할 수 있는 유익한 문제였다. 다른 도메인으로 비슷한 알고리즘을 사용한 문제가 충분히 나올 수 있을 것 같아 유의하면 좋을 것 같다.

---

import sys
input = sys.stdin.readline

def find(x) :
    if root[x] != x:
        root[x] = find(root[x])
    return root[x]

def union(x,y) :
    rootX = find(x)
    rootY = find(y)

    if rootX != rootY :
        if rank[rootX] > rank[rootY] :
            root[rootY] = rootX
            rank[rootX] += rank[rootY]
        elif rank[rootX] < rank[rootY] :
            root[rootX] = rootY
            rank[rootY] += rank[rootX]
        else :
            root[rootY] = rootX
            rank[rootX] += rank[rootY]

T = int(input())
for _ in range(T) :
    F = int(input())
    dict = {}
    count = 0
    root = list(range(F*2))
    rank = [1] * (F*2)
    for _ in range(F) :
        a, b = map(str,input().split())
        if a not in dict :
            dict[a] = count
            count += 1
        if b not in dict :
            dict[b] = count
            count += 1

        first, second = dict[a], dict[b]
        union(first, second)
        print(rank[find(first)])

---

비슷하지만 더 간결한 풀이(시간효율 떨어질 가능성 있음)

import sys
input = sys.stdin.readline

def find(x) :
    if root[x] != x:
        root[x] = find(root[x])
    return root[x]

def union(x,y) :
    rootX = find(x)
    rootY = find(y)

    if rootX != rootY :
        root[rootY] = rootX
        rank[rootX] += rank[rootY]

    print(rank[rootX])

T = int(input())
for _ in range(T) :
    F = int(input())
    count = 0
    root = {}
    rank = {}
    for _ in range(F) :
        a, b = input().split()
        if a not in root :
            root[a] = a
            rank[a] = 1
        if b not in root :
            root[b] = b
            rank[b] = 1 
        union(a, b)

---