🥚문제

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

• 자료 구조
• 분리 집합

---

🥚입력/출력

---

🍳코드

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


def find(a):
    if a == sets[a]:
        return a
    sets[a] = find(sets[a])
    return sets[a]


def union(a, b):
    a = find(a)
    b = find(b)
    if a < b:
        sets[b] = a
    elif a > b:
        sets[a] = b
    else:
        return


def check(a, b):
    if find(a) == find(b):
        print("YES")
    else:
        print("NO")


n, m = map(int, input().split())
sets = [x for x in range(n+1)]  # 자기 자신으로 초기화
for _ in range(m):
    cmd, a, b = map(int, input().split())
    if cmd == 0:
        union(a, b)
    else:
        check(a, b)

---

🧂아이디어

union-find, disjoint set

• [백준 1976] 여행 가자 문제를 풀고 비슷한 유형을 풀고 싶어서 찾아서 푼 문제

• union-find 기법을 이용하여 두 수가 같은 집합에 있다면 YES를, 다른 집합에 있다면 NO를 반환하면 된다.

• 0 a b 형태로 입력이 주어진다면 union(a, b)함수를 호출한다.
  • find(a), find(b)를 통해 a와 b가 속해있는 집합의 값을 찾은 뒤 더 작은 값으로 통일해준다.

• 1 a b형태로 입력이 주어진다면 check(a, b)함수를 호출한다.

  • 이때, a와 b가 같은 집합에 속하는지 찾기 위해서는 sets[a]와 sets[b]를 비교하는 것이 아니라,
    ⭐find(a)와 find(b)의 값이 같은지 비교해야함에 주의한다!

  • 예를 들어 union(1, 3) -> union(7, 6) -> union(3, 7) -> check(1, 7)을 수행한다면

  • sets[a]와 sets[b]를 비교할 때는 NO가 출력되고

  union( 1 , 3 )
  Sets: [0, 1, 2, 1, 4, 5, 6, 7]
  
  union( 7 , 6 )
  Sets: [0, 1, 2, 1, 4, 5, 6, 6]
  
  union( 3 , 7 )
  Sets: [0, 1, 2, 1, 4, 5, 1, 6]
  
  check( 1 , 7 )
  NO
  Sets: [0, 1, 2, 1, 4, 5, 1, 6]

  • find(a)와 find(b)를 비교할 때는 YES가 출력된다

  union( 1 , 3 )
  Sets: [0, 1, 2, 1, 4, 5, 6, 7]
  
  union( 7 , 6 )
  Sets: [0, 1, 2, 1, 4, 5, 6, 6]
  
  union( 3 , 7 )
  Sets: [0, 1, 2, 1, 4, 5, 1, 6]
  
  check( 1 , 7 )
  YES
  Sets: [0, 1, 2, 1, 4, 5, 1, 1]