[백준] 집합의 표현(유니온 파인드) 1717번 (python)

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

풀이 방법

일반적인 유니온 파인드 문제로 해결할 수 있다.

 

실수한 부분

문제를 풀 때 union 함수에서 큰 실수를 했다.

def union(a, b):   
    temp1 = min(find(a), find(b))
    parents[a], parents[b] = temp1, temp1

위와 같은 실수를 했는데 

코드를 자세하게 보면 a와 b의 부모를 찾아 작은 부모로 모두 바꾸어 주었는데

이렇게 코드를 작성하게 된다면 인덱스가 큰 부모를 갖는 원소가 작은 부모를 갖는 원소의 부모로 교체되며 원래 자신의 부모와는 연결이 끊기게 되는 문제가 발생한다.

 

그래서 아래와 같이 코드를 수정했다.

 

def union(a, b):  
    a = find(a)
    b = find(b)
    if a < b:
        parents[b] = a
    else:
        parents[a] = b

 위 코드와 같이 현재 큰 부모를 갖는 원소의 부모를 수정하는 것이 아닌 큰 부모를 갖는 원소의 부모의 부모를 교체해주어야 한다. 

 

전체 코드

import sys
sys.setrecursionlimit(100000)
n, m = map(int, sys.stdin.readline().split())
parents = [ i for i in range(n+1)]

def union(a, b):   
    a = find(a)
    b = find(b)
    if a < b:
        parents[b] = a
    else:
        parents[a] = b

def find(num):
    if parents[num] == num: 
        return num
    parents[num] = find(parents[num])
    return parents[num]

for i in range(m):
    f, a, b = map(int, sys.stdin.readline().split())
    if f == 0:
        union(a, b)
    if f == 1:
        if find(a) == find(b):
            print("YES")
        else:
            print("NO")