[백준] 1717번 집합의 표현(서로소 집합 자료구조)(Union-Find)(Python-파이썬)

백준 1717번 문제입니다. (solved.ac)기준 골드 4 문제 입니다.

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

1717번: 집합의 표현

문제 접근

0부터 n까지 n+1개의 숫자가 있고 {0, 1, ...n} 형식의 집합이 존재합니다. 여기에 합집합 연산과 두  원소가 같은 집합에 포함되어 있는지 확인하는 연산을 수행하려고 한다고 합니다. 

첫째 줄에 n과 m이 주어지는데 n은 집합을 구성하는 마지막 수(0~N까지)이고 m은 입력으로 주어지는 연산의 개수입니다.

합집합은 0 a b의 형태로 주어지고 이것은 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미입니다.

두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어지는데 이것은 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산입니다. a, b의 루트 노드를 확인하여 판별할 수 있습니다.

서로소 집합 자료구조(합집합-찾기 자료구조)를 구현만 하면 아주 간단하게 풀 수 있는 문제입니다. 

서로소 집합 자료구조(합집합-찾기 자료구조)를 잘 모르신다면 아래링크에 자세히 설명해 놓았습니다.

2022.03.05 - [정보[Information]] - 서로소 집합 자료구조(Union-Find)(Python-파이썬)

서로소 집합 자료구조(Union-Find)(Python-파이썬)

 

이 문제에서 주의할 점이 있는데 재귀함수 호출 제한이 걸리는데 이 부분은 아래의 링크에 설명해두었습니다.

2022.01.10 - [파이썬[Python]] - 파이썬[Python] 재귀함수 횟수 제한 풀기(RecursionError 해결방법)

파이썬[Python] 재귀함수 횟수 제한 풀기(RecursionError 해결방법)

-pypy3로 제출하면 메모리 초과 오류가 발생합니다.

-Python3로 제출해야 정답 처리가 됩니다.

정답 코드

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline


def findParent(parent,x) :
    if parent[x] != x:
        parent[x] = findParent(parent, parent[x])
    return parent[x]

def unionParent(parent, a, b) :
    a = findParent(parent,a)
    b = findParent(parent,b)
    if a < b:
        parent[b] = a
    else :
        parent[a] = b

n, m = map(int, input().split())

parent = [0] * (n+1)
for i in range(1, n+1):
    parent[i] = i

for _ in range(m):
    command, a, b = map(int, input().split())

    # 합집합 연산(union)
    if command == 0 :
        unionParent(parent,a , b)
    # 두 원소가 같은 집합에 포함되어 있는지
    # 확인하는 연산
    elif command == 1 :
        if findParent(parent,a) == findParent(parent, b) :
            print("YES")
        else :
            print("NO")