algorithm/문제
[Python] 백준 1717번/집합의 표현/유니온파인드 Union Find
유랄라-
2023. 6. 16. 17:55
반응형
https://www.acmicpc.net/problem/1717
1717번: 집합의 표현
초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작
www.acmicpc.net
⚡️ 문제 설명
전형적인 Union Find 문제!
union find 개념을 안다면 바로 풀 수 있는 문제다.
2023.06.16 - [algorithm/개념] - [Python] Union - Find 유니온 파인드/서로소 집합
[Python] Union - Find 유니온 파인드/서로소 집합
🔎 Union Find (서로소 집합) 란? 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 1. 합집합 (Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 Union (A,B
tral-lalala.tistory.com
⚡️ 해결 방법
union 함수로 자신이 속한 집합을 찾고,
find_parent 함수를 통해 자신의 루트 노드를 찾는다.
루트 노드가 같다면 둘이 같은 집합에 속하기 때문에 YES를 프린트한다.
⚡️ 코드
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
n, m = map(int, input().split())
parent = [ i for i in range(n+1) ]
def find_parent(parent, x):
if parent[x] != x :
parent[x] = find_parent(parent,parent[x])
return parent[x]
def union(parent,x,y):
x = find_parent(parent, x)
y = find_parent(parent, y)
if x<y:
parent[y] = x
else:
parent[x] = y
for _ in range(m):
check, a, b = map(int, input().split())
if check == 0:
union(parent,a,b)
elif check == 1:
if find_parent(parent,a) == find_parent(parent,b):
print("YES")
else:
print("NO")반응형