050 집합의 표현

첫번째 코드

 

유니온 파인드를 처음 접하는 코드였다.

하여 코드는 책을 참고했다.

이론은 이해가 되었는데, 코드에서 살짝 헷갈렸는데 전체적인 감은 잡혔다.

 

find 코드는 부모 노드로 변경

union 코드는 두 노드를 연결

check는 두 대표값이 같은지 확인

 

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

n, m = map(int, input().split())
parent = [0] * (n+1)

for i in range(n+1):
    parent[i] = i

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

def union(a, b):
    a = find(a)
    b = find(b)

    if a != b:
        parent[b] = a

def check(a, b):
    a = find(a)
    b = find(b)

    if a == b:
        return True
    return False

for i in range(m):
    question, a, b = map(int, input().split())

    if question == 0:
        union(a, b)
    else:
        if check(a, b):
            print("YES")
        else:
            print("NO")

 

통과!

DFS, BFS 코드를 작성하면서 익숙해지듯, 유니온파인드도 시간이 필요하다

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/1717.%E2%80%85%EC%A7%91%ED%95%A9%EC%9D%98%E2%80%85%ED%91%9C%ED%98%84

programmers/백준/Gold/1717. 집합의 표현 at main · ornni/programmers