[백준 알고리즘] 집합의 표현 - 유니온 파인드
1717번: 집합의 표현
첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는
www.acmicpc.net
[풀이]
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)
유니온 파인드란? 유니온 파인드는 그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 서로소 집합, 상호 베타적 집합(Disjoint-Set)으로도 불린다. 노드를 합치는 Unio
ip99202.github.io
유니온 파인드(Union Find, Disjoint Set)
유니온 파인드(Union Find)란? 유니온 파인드(Union Find)는 Disjoint Set라고도 불리기도 하며, 이 자료구조는 일상속에서 우리가 은연중에 접하는 자료구조이다. 예를 들어보자. 우리는 학창 시절에 수
www.crocus.co.kr
2. sys 모듈의 재귀제한
import sys
sys.setrecursionlimit(10 ** 6)파이썬 같은 경우, 재귀 깊이 제한은 1000이라 굉장히 얕은 편이다.
그래선지 재귀로 문제를 풀 경우 이 제한에 자주 걸리게 되는데,
문제는 코딩테스트 환경에서는 에러 메시지를 볼 수 없다는 것이다.
만약 재귀를 사용해서 풀어야 하는 문제라면, recursionlimit 거는 건 필수인듯