[백준] 1717번 파이썬 - 유니온파인드

문제요약 (1717. 집합의 표현)

0부터 n까지 있는 집합이 있다. 합집합 연산과 두 원소가 같은 집합에 포함되어 있는지를 확인지 확인하는 연산 두 가지가 주어질 때 각각에 맞는 출력을 제시하시오.

집합을 알맞게 연결해 같은 집합에 속하는지 확인해야하는 문제입니다. 이때 사용할 수 있는 유니온 파인드 알고리즘입니다.

 

 

1717번: 집합의 표현

 

 

풀이를 위한 부연 설명

• 유니온 파인드
  • union과 find 두 가지 연산으로 구성되어 있는 알고리즘
    • union: 노드가 여러개 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 연산
    • find: 두 노드가 같은 집합에 속해 있는지를 확인하는 연산
  • 부모를 저장하는 parent 배열을 만들고 부모를 비교해 같은 집합인지 비교함
• 이 문제에서는 둘이 같은 부모인지 체크하는 함수로 따로 체크할 수 있다.
• 유니온 파인드 에 대한 자세한 개념 설명과 연관 문제는 다음 링크를 참고하면 된다.

 

[코테 알고리즘] 그래프 이론 / 관련 문제

 

코드 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
parent = [i for i in range(n+1)]

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

def union(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        parent[b] = a

def checkSame(a, b):
    a = find(a)
    b = find(b)
    if a == b:
        return True
    return False

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

    if q == 0:
        union(a, b)
    else:
        if checkSame(a, b):
            print("yes")
        else:
            print("no")

 

 

 

기억할 점

• 유니온 파인드 문제 유형을 처음 봤다.
• 파인드는 재귀적으로 구현하고, 유니온은 부모가 다르면 새로 할당해야한다는 사실을 알게 되었다.