백준 실버5 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.
문제
https://www.acmicpc.net/problem/1717
[나의 풀이]
⌛ 시간초과 (68% 통과)
def find(x):
if parent[x]!=x:
return find(parent[x])
return x
def union(a,b):
a = find(a)
b = find(b)
if a<b:
parent[b]=a
else:
parent[a]=b
n,m = map(int,input().split())
parent = {i:i for i in range(n+1)}
check = []
for _ in range(m):
hap, a,b = map(int,input().split())
check.append((hap,a,b))
for case in check:
hap, a,b = case
if hap==0:
union(a,b)
else:
if find(a)==find(b):
print("YES")
else:
print("NO")
n+1까지의 숫자들이 존재하고 합집합인 두 수(a,b)를 알려주며 특정 시점마다
입력되는 두 수(x,y)가 합집합 관계인지 구하는 문제입니다.
문제를 이해하고 Union-Find라고 직감하여 바로 구현하였지만 테스트 케이스(68%)에서 재귀함수 호출 초과 에러가 발생하여 다른 풀이를 참고하였습니다.🐢🐢🐢
[다른 사람의 풀이1]
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
n,m = map(int,input().split())
parent = {i:i for i in range(n+1)}
check = []
for _ in range(m):
hap, a,b = map(int,input().split())
check.append((hap,a,b))
for case in check:
hap, a,b = case
if hap==0:
union(a,b)
else:
if find(a)==find(b):
print("YES")
else:
print("NO")
'나의 풀이'와 같이 Union-Find를 활용한 풀이이되, Find()하는 과정에서 시간복잡도를 줄인 방식입니다.🕊️🕊️🕊️
parent[x] = find(parent[x])
의 표현으로 '나의 풀이'처럼 현재 노드의 바로 상위 부모로 초기화하는 것이 아닌 각 노드별로 최상위 부모노드를 가리키는 방식으로 초기화하여 시간복잡도를 줄인 것이 포인트였습니다.
[다른 사람의 풀이2]
import sys
input = sys.stdin.readline
# disjoint set & union-find
n, m = map(int,input().split())
parent = [i for i in range(n+1)]
def find(c):
if(parent[c] == c): return c
parent[c] = find(parent[c])
return parent[c]
def union(ca,cb):
rootOfca = find(ca)
rootOfCb = find(cb)
if not rootOfca == rootOfCb:
parent[rootOfCb] = rootOfca
def check(ca,cb):
if find(ca) == find(cb):
return True
else:
return False
# finding answer
ans = []
for i in range(m):
flag, a, b = map(int,input().split())
if flag == 0 :
union(a,b)
else:
if check(a,b):
ans.append("YES")
else:
ans.append("NO")
for i in range(len(ans)):
print(ans[i])
'다른 사람의 풀이1'과 같이 각 노드별 최상위 부모로 초기화한 풀이이며 두 수(ca,cb)가 같은 집합인지 확인하기 위해 check()함수화 해준 모습입니다.🐇🐇🐇
감사합니다.