백준 - 1717번(유니온 파인드, 재귀, 집합)

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

1717번: 집합의 표현

문제 자체가 이해가 어렵지는 않은 문제다.

이 문제를 풀기 위해서는 유니온 파인드가 뭔지 알아야 한다.

그래프 풀이법의 일종으로 볼 수 있다.

노드들을 합치고(union), 부모를 찾아준다(find)

 

일련의 과정은 다음과 같다.

1. 원소 두 개를 입력받고 Union 함수를 호출한다.

 

2. 입력받은 원소의 부모를 find 함수를 이용해서 '재귀적으로'  찾아 준다. 

 

3. 부모는 배열에서의 인덱스의 값과 본인이 가지고 있는 값이 같을 것이다. 해당 조건을 만족하면 return, 왜 이런 조건을 만족해야 하냐면 배열을 처음 만들 때 0번째에 0, 1번째에 1, 2번째에 2... 이런 식으로 만들었다. 부모의 노드는 쉽게 생각하면 기준을 의미하기도 한다.

기준이 초기값과 바뀐다면 우리는 그걸 기준이라고 부를 수 없다.

 

4. 입력받은 원소 두 개의 부모 노드를 반환받았으면 둘 중 더 큰 좌표의 값을 작은 원소로 바꿔 준다. 반대가 돼도 상관없다.

 

5. 부모가 같은지 찾는 것은 find 함수를 통해서 찾으면 된다.

 

import sys
sys.setrecursionlimit(100000)
n,m = map(int,sys.stdin.readline().split())

arr = []
for i in range(n+1):
    arr.append(i)

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

def union(a,b):
    a = find(a)
    b = find(b)
    arr[max(a,b)] = min(a,b)


for i in range(m):
    ord,a,b = map(int,sys.stdin.readline().split())

    if ord == 0:
        union(a,b)
    else:
        if find(a) == find(b):
            print('YES')
        else:
            print('NO')

재귀의 개념이 잘 잡혀 있다면 이해가 수월하다.

역시 재귀가 들어가면 재밌다.