컴알 수업에서 하는 알고리즘으로 백준 풀어볼 거다
티어 : 🥇2
태그 : 유니온 파인드
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)])
'📊 Algorithm > BOJ' 카테고리의 다른 글
⚠︎ 백준 - 9372 상근이의 여행 ✈️ (0) | 2024.04.10 |
---|---|
⚠︎ 백준 - 6469 전력난⚡️ (0) | 2024.04.09 |
⚠︎ 백준 - 1774 우주신👽과의 교감 (4) | 2024.04.08 |
⚠︎ 백준 - 2447 별 찍기 - 10 (0) | 2024.04.08 |
⚠︎ 백준 - 24267 알고리즘 수업 - 알고리즘의 수행 시간 6/ 24313 알고리즘 수업 - 점근적 표기 1 (3) | 2024.04.06 |