(Python/🥇4)백준알고리즘 1717번: 집합의 표현

집합의 표현 바로가기

백준알고리즘 집합의 표현

 

문제:

 

초기에 n+1개의 집합 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오.

입력:

 

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

출력:

 

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

 

풀이:

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
sys.setrecursionlimit(10**6)

N, M = map(int,sys.stdin.readline().split(" "))
parents = [i for i in range(N+1)] # 부모는 자기자신

def find(x):
    if parents[x] != x:
        parents[x] =  find(parents[x])
    return parents[x]
def union(x,y): # 작은 수로 합 해주면 됨.
    xx = find(x)
    yy = find(y)
    if xx > yy:
        parents[xx] = yy
    else:
        parents[yy] = xx


for i in range(M):
    status, V, E = map(int,sys.stdin.readline().split(" "))
    if status == 0:
        union(V,E)
    else:
        if find(V) == find(E):
            print("YES")
        else:
            print("NO")

 

union-find 기본문제이다. 하지만 find 부분을 경로압축기법을 사용해야한다.

 

def find(x):
    if parents[x] != x: # 부모가 자기 자신이 아니면 부모를 찾아야함
        return find(parents[x]) # 부모의 부모를 찾는다.
    return parents[x] # 자기자신이면 자기를 리턴함

이렇게 사용하면 시간초과가 난다.

 

두 개의 차이점은 압축경로기법에서는 parents에 저장을 해 놓는것이다.