[맛있는물회] [파이썬] <백준 알고리즘> 1717번 "집합의 표현"

문제 조건

---

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

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

 

Input

---

첫째 줄에 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이며 같을 수도 있다.

 

Output

---

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

 

생각한 아이디어

---

disjoint-set, Union-Find 문제

 

사실 구현하는 로직을 이해하고 있다면 간단하게 풀 수 있는 문제지만, 로직 자체가 막 익숙하지는 않다는 것...

 

https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

[알고리즘] Union-Find 알고리즘 - Heee's Development Blog

아주 설명을 잘해주신다.

 

쉽게말하면 

시작할때 초기화 상태는 각각 root 즉, parent root 가 자신이다.

 

만약 a이랑 b를 union 하고 싶다.

그렇다면 a와 b의 parent root를 찾는다.

그 다음 b의 parent root에 a의 parent root를 연결시키면된다.

 

이렇게 말로 표현하니깐 좀 이해가 잘 안될 수 도 있는데 그림으로 그려보면서 이해하면 좋을 것 같다.

disjoint-set 에 대한 문제들을 더 풀어봐야겠다 !!

 

소스코드

import sys
import math
from collections import deque
import copy
input=sys.stdin.readline
INF=sys.maxsize

def find(parent,n):
    tmp=n
    while 1:
        if parent[tmp]==tmp:#루트를 찾음
            return tmp
        tmp=parent[tmp]

if __name__ == "__main__":
    n,m=map(int,input().split())
    arr=[list(map(int,input().split())) for _ in range(m)]
    parent=[i for i in range(0,n+1)]

    for val in arr:
        a,b=val[1],val[2]
        if val[0]==0:
            parent[find(parent,b)]=find(parent,a)
        else:
            if find(parent,a)==find(parent,b):
                print('YES')
            else:print('NO')

 

*파이썬 문법 정리