⚠︎ 백준 - 4195 친구 네트워크

컴알 수업에서 하는 알고리즘으로 백준 풀어볼 거다

---

티어 : 🥇2

태그 : 유니온 파인드

4195번: 친구 네트워크

---

find / union 함수 따로 역할 나눠서 구현

 

find : 노드의 부모 노드 찾기

union : 두 개 노드 묶기

 

수업 코드

def find(parent, i): 
    if parent[i] != i:
        parent[i] = find (parent, parent[i]) 
    return parent[i]

def union(parent, rank, x, y): 
    if rank[x] < rank[y]:
        parent[x] = y
    elif rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[y] = x 
        rank[x] += 1

- rank 배열을 사용하여 두 트리를 병합할 때 높이를 고려하고, 불필요한 트리 성장을 방지하기

---

무지성 코드짜기

import sys

T = int(sys.stdin.readline())

# 부모,루트 노드 찾기
def find(name):
    if parent[name] != name :
        parent[name] = find(parent[name]) # 경로 압축
    return parent[name]

# 묶기 , 부모,루트 노드 연결
def union(a_name,b_name):
    parent[find(a_name)] = find(b_name)


for _ in range(T):
    # 각 노드 부모,루트 저장 리스트
    parent = {}

    N = int(sys.stdin.readline())

    for _ in range(N):
        a_name, b_name = map(sys.stdin.readline())

        if a_name not in parent:
            parent[a_name] = a_name
        if b_name not in parent:
            parent[b_name] = b_name

        union(a_name,b_name)

        parent_name = find(a_name)

        print(parent.values.count(parent_name))

시간초과남.

 

최적화 시도

 

1. 친구 네트워크의 크기 추적

모든 입력에 대해 매번 친구 네트워크의 크기 출력시 parent 딕셔너리의 값을 순회

=> 대신, 각 노드에 대해 네트워크의 크기를 추적하는 별도의 딕셔너리(network_size)를 사용하기

 

 

2. "Union by Rank" 최적화 (경로 압축 Path Compression)

network_size를 사용하여 각 루트 노드(즉, 각 네트워크)의 크기를 관리 (불필요한 트리 성장 막기)

import sys

T = int(sys.stdin.readline())

def find(name):
    if parent[name] != name :
        parent[name] = find(parent[name])
    return parent[name]

#  경로 압축
def union(a_name, b_name):
    root_a = find(a_name)
    root_b = find(b_name)
    if root_a != root_b:
        if network_size[root_a] < network_size[root_b]:
            parent[root_a] = root_b
            network_size[root_b] += network_size[root_a]
        else:
            parent[root_b] = root_a
            network_size[root_a] += network_size[root_b]


for _ in range(T):
    # 각 노드 부모노드 저장 딕셔너리
    parent = {}
    network_size = {} # 친구 네트워크의 크기 추적용 딕셔너리
    N = int(sys.stdin.readline())
    for _ in range(N):
        a_name, b_name = input().split()
        if a_name not in parent:
            parent[a_name] = a_name
            network_size[a_name] = 1
        if b_name not in parent:
            parent[b_name] = b_name
            network_size[b_name] = 1

        union(a_name, b_name)

        print(network_size[find(a_name)])

므밈미