[알고리즘] 26일차 (집합 표현하기) #백준1717번

08-2 유니온 파인드

• 유니온 파인드는 일반적으로 여러 노드가 있을 때, 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다.
• union(a, b) = A U B (For a E A & b E B)
• find(a) = A 집합의 대표 노드를 반환한다. (For a E A)

[유니온 파인드 원리 이해하기]
1. 표현 방법: 1차원 리스트, 처음에는 각 노드가 연결 X -> 각 노드가 대표 노드, 리스트는 자신의 인덱스 값으로 초기화한다.
2. 2개의 노드를 선택해 각각 대표 노드를 찾아 연결하는 union 연산을 수행한다. 자식 노드로 들어가는 노드값을 대표 노드 값으로 변경한다.
3. find 연산은 자신이 속한 집합의 대표 노드를 찾는 연산이지만 단순히 대표 노드만을 찾는 것이 아닌, 그래프를 정돈하고 시간 복잡도를 줄인다. (O(1)로 연산 속도 변경)

[find 연산 작동 원리]
1. 대상 노드 리스트에 index값과 value값이 동일한지 확인한다.
2. 동일하지 않으면 value값이 가리키는 index 위치로 이동한다.
3. 이동 위치의 index값과 value값이 같을 때까지 1~2번 과정을 반복한다. (재귀 함수로 구현)
4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드 값을 대표 노드 값으로 변경한다.

📌 문제 050) 집합 표현하기

시간 제한 2초, 골드 IV, 백준 1717번

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

입력

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

7 8 # 원소 개수, 질의 개수
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

출력

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

NO
NO
YES

제한

1 ≤ n ≤ 1,000,000 
1 ≤ m ≤ 100,000 
0 ≤ a, b ≤ n
a, b는 정수
a와 b는 같을 수도 있다.

1단계 문제 분석

• 최대 원소의 개수 1,000,000과 질의 개수 100,000이 큰 편이므로 경로 압축이 필요한 전형적인 유니온 파인드 문제이다.

1. 처음은 노드 연결 X, 각 노드 = 대표 노드, 각 노드를 자기 인덱스 값으로 초기화한다.
2. find 연산으로 특정 노드를 찾고, union 연산으로 2개의 노드를 이용해 각 대표 노드를 찾아 연결한다. 그리고 질의한 값에 따라 결과를 반환한다.

2단계 슈도 코드

N(원소 개수) M(질의 개수)
parent(대표 노드 저장 리스트)

# find 연산
find(a):
	a가 대표 노드면 리턴
    아니면 a의 대표 노드 값을 find(parent[a]) 값으로 저장 - 재귀 함수 형태

# union 연산
union(a, b):
	a와 b의 대표 노드 찾기
    두 원소의 대표 노드끼리 연결

# checkSame -> 두 원소가 같은 집합인지 확인
checkSame(a, b):
	a와 b의 대표 노드 찾기
    두 대표 노드가 같으면 true
    아니면 false return

for N만큼 반복:
	대표 노드를 자기 자신으로 초기화

for M만큼 반복:
	if 질의가 0:
    	집합 합치기 -> union 연산
    else:
    	같은 집합 원소인지 확인하고 결괏값 출력

3단계 코드 구현

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
parent = [0] * (N + 1)

def find(a): # find 연산
    if a == parent[a]:
        return a
    else:
        parent[a] = find(parent[a]) # 재귀 형태로 구현 -> 경로 압축 부분
        return parent[a]

def union(a, b): # union 연산 대표 노드끼리 합치기
    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 i in range(0, N + 1):
    parent[i] = i

for i in range(M):
    question, a, b = map(int, input().split())
    if question == 0:
        union(a, b)
    else:
        if checkSame(a, b):
            print("YES")
        else:
            print("NO")