[백준 알고리즘] 집합의 표현 - 유니온 파인드

 

1717번: 집합의 표현

 

[풀이]

def find(x) :
    if parent[x] < 0:
        return x
    else :
        parent[x] = find(parent[x])
        return parent[x]
        
def union(a,b) :
    a = find(a)
    b = find(b)
    if a != b :
        parent[a] = b

import sys
sys.setrecursionlimit(10 ** 6)

n, m = map(int,sys.stdin.readline().rstrip().split())

parent = [-1] * (n+1) #초기 집합

for _ in range(m):
    cmd, a, b = map(int,sys.stdin.readline().rstrip().split())
    if cmd == 0: # 유니온 수행
        union(a,b)
    else:
        if find(a) == find(b): #파인드 수행 / 루트가 같다
            print("YES")
        else: #다름
            print("NO")

 

1. 유니온 파인드

난 여태 알고리즘보다는 자료구조에 대해 공부를 많이 했던 것 같다.

큐, 스택, 해시, 힙 그리고 이런 자료의 특성을 이용해 문제를 해결하는.

유니온 파인드 굉장히 기초적인 그래프 알고리즘인것 같아 잘 알아두면 확실히 도움 될듯!

특히 코테세상에 판치고 있는 DFS/BFS 배우기 전에 해두면 좀 좋을 거 같아

[참고자료]

유니온 파인드(Union-Find)

유니온 파인드(Union Find, Disjoint Set)

 

2. sys 모듈의 재귀제한

import sys
sys.setrecursionlimit(10 ** 6)

파이썬 같은 경우, 재귀 깊이 제한은 1000이라 굉장히 얕은 편이다.

그래선지 재귀로 문제를 풀 경우 이 제한에 자주 걸리게 되는데,

문제는 코딩테스트 환경에서는 에러 메시지를 볼 수 없다는 것이다. 

만약 재귀를 사용해서 풀어야 하는 문제라면, recursionlimit 거는 건 필수인듯