[코딩 테스트 연습(파이썬/Python)] 백준 1717번 _ 집합의 표현

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

1717번: 집합의 표현

[문제]

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

 

[입력]

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

[출력]

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

 

[아이디어]

1) Union-FInd라는 트리형태의 자료구조에 관한 문제라고 한다.

2) 합집합을 직접 반복하기에는, 점점 업데이트 해야하는 집합의 수가 너무 많아진다.

(원소 i,j가 등장했을 때 i,j를 포함하는 모든 집합들을 탐색한 후 업데이트 하는 것은 시간초과를 야기한다.)

3) 따라서 (n+1)개의 원소를 갖는 리스트 t에 각 집합의 대푯값만(root)을 저장하며 업데이트한다.

4) 두 집합을 합집합한다는 것을, 두 집합의 대푯값을 일치시키는 것으로 생각한다.

5) 숫자 1이 등장했을 때, 대응되는 두 집합의 대푯값이 같은지 확인한 후 yes/no를 출력한다.

 

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
n,m = map(int,input().split())
t=[i for i in range(n+1)]
def root(a):
    if t[a]==a:
        return a
    t[a]=root(t[a])
    return t[a]
def union(a,b):
    x=root(a);y=root(b)
    if x==y:
        return
    t[y]=x
for _ in range(m):
    a,b,c=map(int,input().split())
    if a==0:
        union(b,c)
    elif a==1:
        print('YES' if root(b)==root(c) else 'NO')

자료구조 문제는 관련 지식이 있는지 여부가 너무 크게 작용하는 것 같다. 대표적인 문제들은 공부를 좀 하고 푸는게,,