[백준] 1717번 집합의 표현 _ Python

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

1717번: 집합의 표현

 

 

 

---

 

1. Preview

시간 복잡도: O(M*a(N))

   M : 연산 갯수

   a(N) : 경로 압축한 find()의 시간 복잡도

 

공간 복잡도: O(N)

 

참고 : https://dheldh77.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9C%A0%EB%8B%88%EC%98%A8%ED%8C%8C%EC%9D%B8%EB%93%9CUnion-Find-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-1 (경로 압축, 개인 고찰)

 

유형: disjoint set(분리집합), union-find

 

 

---

 

2. 초기 접근 방법

일반적인 union-find 알고리즘으로 풀었다.

1) 먼저 집합에 속하는 것을 분류할 수 있게끔, 각 노드에 대한 루트를 저장하는 역할을 하는 루트 배열을 생성한다. (초기값은 자기 자신)

 

그리고 다음 연산을 정의한다.

2) find() : 재귀로 루트 연산 조회 + 경로 압축(부모 노드가 아닌 루트 노드를 저장)

3) union() : 합집합 연산으로 2개의 루트 노드 중 1개로 통일

 

 

---

 

3. 생각

당연히 둘 다 통과되는 코드이지만, 그냥 한 번 해보았다 ㅎㅎ..

 

1) 해당 집합에서 루트 노드를 최솟값으로 유지하는 방식

def union(x, y):
    rootX = find(x)
    rootY = find(y)

    if rootX < rootY:
        parent[rootY] = rootX
    else:
        parent[rootX] = rootY

 

 

2) 대소 관계는 신경 쓰지 않고, 무조건 x를 기준으로 합집합하는 방식

def union(x, y):
    rootX = find(x)
    rootY = find(y)

    if rootX != rootY:
        parent[rootY] = rootX
    # else:
    #     parent[rootX] = rootY

 

 

---

 

4. 코드

# 0 : 합집합
# 1 : 두 원소가 같은 집합에 포함되어 있는지

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

def find(x):
    if x == parent[x]:
        return x

    parent[x] = find(parent[x]) # 경로 압축 최적화
    return parent[x]

def union(x, y):
    rootX = find(x)
    rootY = find(y)

    if rootX < rootY:
        parent[rootY] = rootX
    else:
        parent[rootX] = rootY


# m : 입력으로 주어지는 연산의 개수
N, M = map(int, input().split())

# 초기 루트 노드는 자기 자신으로 초기화
parent = [0 for _ in range(N+1)]
for i in range(N+1):
    parent[i] = i

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

    # 합집합 연산
    if op == 0:
        # 루트 노드가 다르면
        if find(a) != find(b):
            union(a, b)

    # 두 원소가 같은 집합에 포함되어 있는지
    # 즉, 같은 루트 노드를 가지고 있는지
    else:
        if find(a) != find(b):
            print("NO")
        else:
            print("YES")