[백준 파이썬] #1717. 집합의 표현

풀기 전 생각해보기😮

• 재귀 호출 깊이를 지정해주지 않았을 때 recursion error가 발생했다.
• import sys 또한 빠뜨리지 않도록 주의하자 (import를 빼먹으면 name error 발생)

 

---

풀이🛫

import sys
sys.setrecursionlimit(10**5)

# 서로소 집합 문제
# pypy3 채점

def find(x):    # x의 부모 값을 return
    if x == p[x]:       # 자기 자신을 부모로 갖는 경우
        return p[x]     # 그대로 return
        # return x를 해도 동일함, 그러나 return 값을 p[x]로 맞춰주기 위해 p[x]로 연습하자

    # 자기 자신을 부모로 갖지 않는 경우
    p[x] = find(p[x])   # path compression 진행
    return p[x]         # x의 부모 값을 return

def union(x, y):
    p[find(y)] = find(x)    # y값의 부모를 x값의 부모로 변경


n, m = map(int, input().split())
p = [i for i in range(n+1)]     # p: 부모로 가리키고 있는 값을 나타내는 리스트

for _ in range(m):
    ord, a, b = map(int, input().split())
    if ord == 0:    # a, b의 집합을 하나로 합친다
        union(a, b)
    else:   # ord == 1일 때 합집합 여부 확인
        if find(a) == find(b):  # a의 부모 노드와 b의 부모 노드가 같다 → 같은 집합이다
            print("YES")
        else:
            print("NO")

 

핵심 정리🎁

def find(x):    # x의 부모 값을 return
    ...

    p[x] = find(p[x])   # path compression
    return p[x]

 

path compression?

find(x) 과정에서 만나는 모든 노드들이 직접 (최종적으로 가리키는) 부모를 가리킬 수 있도록 정보를 변경하는 것을 말한다. path compression을 거치지 않게되면 편향적인 트리구조가 생성되고, 간선의 수만큼 재귀호출이 필요해지는 문제가 발생한다. 이는 시간과 메모리상에서 큰 비효율을 초래하게 된다.

 

 

링크💎

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

후기 😎

def union(x, y):
    # test 1: 257616kb 4996ms
    p[find(y)] = find(x)    # y값의 부모를 x값의 부모로 변경

    # test 2: 278440kb 5008ms
    if find(x) < find(y):
        p[find(y)] = find(x)
    else:
        p[find(x)] = find(y)

궁금증

• 구글링 하다보면 test2 방식으로 풀이하신 분들이 많았는데 굳이 저렇게 작성해야 하나? 하는 의문이 남아있다.
• test1 방식으로 풀이했을 때도 동일하게 정답을 확인했고, 오히려 시간과 메모리가 단축되는 것을 확인했다.