[백준] 1717번 - 집합의 표현

문제 링크 : https://www.acmicpc.net/problem/1717

 

문제

초기에 𝑛+1개의 집합 {0},{1},{2},…,{𝑛}이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

 

입력

첫째 줄에 𝑛, 𝑚이 주어진다. 𝑚은 입력으로 주어지는 연산의 개수이다. 다음 𝑚개의 줄에는 각각의 연산이 주어진다. 합집합은 0 𝑎 𝑏의 형태로 입력이 주어진다. 이는 𝑎가 포함되어 있는 집합과, 𝑏가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 𝑎 𝑏의 형태로 입력이 주어진다. 이는 𝑎와 𝑏가 같은 집합에 포함되어 있는지를 확인하는 연산이다.

 

출력

1로 시작하는 입력에 대해서 𝑎와 𝑏가 같은 집합에 포함되어 있으면 "YES" 또는 "yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.

 

풀이

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

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

def find(i):
    if linked[i] != i:
        linked[i] = find(linked[i])
        return linked[i]
    else:
        return i
    
def set(i,j):
    fi = find(i)
    fj = find(j)
    linked[fj] = fi

for M in range(m):
    l, a, b = map(int, input().split())
    if l == 0:
        set(a,b)
    elif l == 1:
        if find(a) == find(b):
            print('YES')
        else:
            print('NO')

 

해설

• 유니온 파인드라는 이론을 사용하여 푼 문제
  • union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산
  • find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산
• 간단히 말하면 집합으로 합치는데 최상단에 대표 노드를 정하여 이 노드를 중심으로 집합을 생성하는 것이다.
• 이렇게 하면 대표 노드에서 뻗어나온 것들은 모두 연결되어있다는 사실을 빠르게 알 수 있다.

 

참고

Do it! 알고리즘 코딩 테스트 - 파이썬 편 pg.263