[백준(BOJ)] #1717- 집합의 표현 (파이썬, Python3)

문제

 

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

1717번: 집합의 표현

 

---

문제 풀이

이 문제는 다른 거 할 거 없이 Union-Find 알고리즘만 적용하면 되는 문제입니다.

 

2022.07.24 - [알고리즘/개념] - [파이썬으로 배우는 알고리즘] Union-Find 알고리즘

[파이썬으로 배우는 알고리즘] Union-Find 알고리즘

 

각 줄에서 맨 처음에 오는 숫자는 연산을 의미합니다.

 

0은 union

1은 find

 

따라서 이 연산에 맞게 각 노드의 연결관계를 set 또는 get 하시면 됩니다!

Union-Find 알고리즘은 위의 글에서 세세하게 설명하니 참고하셔서 풀면 될 것 같네요 ㅎ

 

---

구현

코드

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

# 노드의 루트 노드를 찾는 함수
def find(v):
    if v != rootList[v]:
        rootList[v] = find(rootList[v])
    return rootList[v]
    
# 루트 노드에 따라 합!
def union(v1, v2):
    v1 = find(v1)
    v2 = find(v2)
    
    if v1 < v2:
        rootList[v2] = v1
    else:
        rootList[v1] = v2
        
# 두 노드가 같은 집합에 있는지 확인하는 함수
def is_same_sec(v1, v2):
    v1_root = find(v1)
    v2_root = find(v2)
    if v1_root == v2_root:
        return True
    else:
        return False
        
if __name__ == "__main__":
    n, m = map(int, input().split())
    rootList = list(range(n+1))
    
    for _ in range(m):
        op, v1, v2 = map(int, input().split())
        if op == 0:
            union(v1, v2)
        elif op == 1:
            if is_same_sec(v1, v2):
                print('YES')
            else:
                print('NO')

 

결과