[백준] 1717번 집합의 표현 파이썬 풀이

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

1717번: 집합의 표현

---

1. 접근 방식

• union-find 방식

초기 리스트

인덱스를 원소 값으로 갖는, 길이 (n + 1)짜리 리스트를 생성한다. 인덱스가 3이라면, 인덱스 3은 정수, list[3]은 해당 정수가 속한 집합을 의미한다.

 

1과 3 합치고, 4와 5 합치기

따라서 정수 1과 3을 합치고, 정수 4와 5를 합치면 리스트는 위와 같아진다.

 

이처럼 여러 숫자(노드)가 있고, 두 개의 숫자를 선택하여 두 개가 같은 집합(그래프)에 속하는지 판별하는 알고리즘이 union-find 알고리즘이다.

 

 

• 파이썬의 재귀 깊이 제한 조정

import sys
sys.setrecursionlimit(1000000)

정답 코드에 있는 find_parent()라는 메서드의 재귀 깊이는 최대 1,000,000번이다. n의 크기가 최대 백 만이기 때문이다. 그러나 파이썬3 기준 가능한 최대 재귀 깊이는 1,000밖에 되지 않는다. 따라서 위 코드로 재귀 깊이 한도를 변경해야 한다.

 

 

 

2. 정답 코드

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

def find_parent(x):
    if parents[x] == x:
        return x
    parents[x] = find_parent(parents[x])
    return parents[x]

def union(a, b):
    a = find_parent(a)
    b = find_parent(b)

    if a > b:
        parents[a] = b
    else:
        parents[b] = a

def is_same_set(a, b):
    a = find_parent(a)
    b = find_parent(b)

    return "YES" if a == b else "NO"

# main
n, m = map(int, input().split())
parents = [i for i in range(n + 1)]

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

    if op == 0:
        union(a, b)
    else:
        print(is_same_set(a, b))