[Baekjoon Online Judge] 백준 1717번 집합의 표현(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1717번 집합의 표현

(Python)

(글쓴날 : 2020.05.16)

 

---

* Baekjoon Online Judge, 백준 1717번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1717번 집합의 표현

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

---

2) 풀이 과정

* 시간 복잡도 : O(α(n), α : 아커만 함수)

 

0부터 n까지 각각 n+1개의 집합을 이루고 있을 때, 합집합 연산과 두 원소가 같은 집합에 포함되어 있는지 확인하는 연산을 수행하는 문제입니다.

 

저의 경우, 유니온 파인드를 적용하였으며, Python을 사용했습니다.

유니온 파인드 그 자체를 구현하는 기본 문제여서, 별다른 풀이 과정 없이 유니온 파인드를 구현해 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
 
def find(target):
    if target == parent[target]:
        return target
 
    parent[target] = find(parent[target])
    return parent[target]
 
 
def union(a, b):
    a = find(a)
    b = find(b)
 
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
 
 
n, m = map(int, input().split())
parent = [ i for i in range(n + 1)]
 
for _ in range(m):
    oper, a, b = map(int, input().split())
 
    if oper:
        findA = find(a)
        findB = find(b)
 
        if findA == findB:
            print("YES")
        else:
            print("NO")
    else:
        union(a, b)

---