서로소 집합 (UNION-FIND) 문제

조현수·2023년 2월 19일
문제 유형서로소 집합유니온 파인드
0

알고리즘 활용하는 문제 유형들

목록 보기
24/33

👻 서로소 집합(Disjoint Sets)

서로소 집합이란, 공통 원소가 없는 두 집합을 의미한다.

  • {1,2}, {3,4}는 서로소 관계이다.

서로소 집합 자료구조

⚽ 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다.
⚽ 서로소 집합 자료구조는 두 종류의 연산을 지원한다.

  • 합집합(Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
  • 찾기(Find) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

😀 서로소 집합 자료구조는 유니온 파인드라고 불림





⚽ 여러 개의 합집합 연산이 주어졌을 때, 서로소 집합 자료구조의 동작 과정에 대해 알아보자.

  1. 합집합(Union)연산을 확인하여, 서로 연결된 두 노드 A,B를 확인한다.
  2. A와 B의 루트 노드 A' B'를 각각 찾는다
  3. A'를 B'의 부모 노드로 설정한다
  4. 모든 합집합(Union)연산을 처리할 때까지 1번의 과정을 반복한다.



💨 서로소 집합 자료구조 : 동작과정

  • 처리할 연산들 : 𝑈𝑛𝑖𝑜𝑛(1,4), 𝑈𝑛𝑖𝑜𝑛(2,3), 𝑈𝑛𝑖𝑜𝑛(2,4), 𝑈𝑛𝑖𝑜𝑛(5,6)

  • 초기 단계 : 노드의 개수 크기의 부모 테이블을 초기화한다.

    • 직관적인 값. 즉 모두 부모를 자기 자신으로 설정하고 있도록 한다.

  • 즉 초기 단계에서는 6개의 노드가 서로 다른 집합이라고 볼 수 있다. (이때 6개의 집합은 모두 서로 다른 집합으로 분류되고 있으며, 각각 원소가 1개씩 존재하기 때문에 부모가 서로 다르다.)

⚽ 처리할 연산들 : 𝑈𝑛𝑖𝑜𝑛(1,4), 𝑈𝑛𝑖𝑜𝑛(2,3), 𝑈𝑛𝑖𝑜𝑛(2,4), 𝑈𝑛𝑖𝑜𝑛(5,6)

  • [step 1] 노드 1과 노드 4의 루트 노드를 각각 찾는다. 현재 루트 노드는 각각 1과 4이므로 더 큰 번호에 해당하는 루트 노드 4의 부모를 1로 설정한다.

⚽ 처리할 연산들 : 𝑈𝑛𝑖𝑜𝑛(1,4), 𝑈𝑛𝑖𝑜𝑛(2,3), 𝑈𝑛𝑖𝑜𝑛(2,4), 𝑈𝑛𝑖𝑜𝑛(5,6)

  • [step 2] 노드 2와 노드 3의 루트 노드를 각각 찾는다. 현재 루트노드는 각각 2와 3이므로 더 큰 번호에 해당하는 루트 노드 3의 부모를 2로 설정한다.

⚽ 처리할 연산들 : 𝑈𝑛𝑖𝑜𝑛(1,4), 𝑈𝑛𝑖𝑜𝑛(2,3), 𝑈𝑛𝑖𝑜𝑛(2,4), 𝑈𝑛𝑖𝑜𝑛(5,6)

  • [step 3] 노드 2와 노드 4의 루트 노드를 각각 찾는다. 현재 루트 노드는 각각 2와 1이므로 더 큰 번호에 해당하는 루트 노드 2의 부모를 1로 설정한다.

🎈 여기서 유의할 점은

현재 이 테이블은 부모노드에 대해서 기록하고 있는 테이블이라고 볼 수 있다. 확인해보면 현재 3번노드와 4번노드는 같은 집합으로 연결되어 있는데, 하지만 당장 3번노드의 부모를 확인해보면 2번노드를 가리키고 있다. 4번 노드와 부모가 다른걸 확인할 수 있다.

그래서 실제로는 두 원소가 같은 집합에 포함되어 있는지 확인하기 위해서 그 루트노드를 찾을 수 있도록 해야한다!!! 즉 3번노드의 부모를 확인한 뒤(2번노드) 다시한번 이 노드의 부모를 계속해서 찾아가면서 1번노드까지 갔을 때 1번노드는 자기 자신이 부모이기 때문에 1번노드가 루트라는걸 알 수 있다. 그렇기 때문에 3번노드의 루트노드인 1와 4번노드의 루트노드인 1이 서로 같기 때문에 3번노드와 4번노드는 서로 같은 집합에 속해 있다고 판단할 수 있다.

  • 여기서 이 테이블은 부모 테이블이고 루트 테이블이 아니라는 점을 유의해서 생각하자 (이 얘기를 하는 이유는 밑에서 설명)

⚽ 처리할 연산들 : 𝑈𝑛𝑖𝑜𝑛(1,4), 𝑈𝑛𝑖𝑜𝑛(2,3), 𝑈𝑛𝑖𝑜𝑛(2,4), 𝑈𝑛𝑖𝑜𝑛(5,6)

  • [step 4] 노드 5와 노드6의 루트 노드를 각각 찾는다. 현재 루트노드는 각각 5와 6이므로 더 큰 번호에 해당하는 루트노드 6의 부모를 5로 설정한다.

🏈 서로소 집합 자료구조 : 연결성

  • 서로소 집합 자료구조에서는 연결성을 통해 손쉽게 집합의 형태를 확인할 수 있다.

🚀 기본적인 형태의 서로소 집합 자료구조에서는 루트 노드에 즉시 접근할 수 없다.

  • 루트 노드를 찾기 위해 부모 테이블을 계속해서 확인하며 거슬러 올라가야 한다.

🚀 다음 예시에서 노드 3의 루트를 찾기 위해서는 노드 2를 거쳐 노드 1에 접근해야 한다

서로소 집합 자료구조 : 기본적인 구현 방법

import sys
sys.stdin = open("input.text", "rt")

#노드의 개수와 간선(Union 연산)의 개수 입력받기
v,e = map(int, input().split())
parent = [0] * (v+1)  #부모 테이블 초기화 1번 인덱스부터 사용

#부모 테이블상에서 부모를 자기 자신으로 초기화
for i in range(1,v+1):
    parent[i] = i

#특정 원소가 속한 집합을 찾기
def find_parent(parent, x):   #(부모테이블, 노드의 번호) 인자로 들어옴
    #루트 노드를 찾을 때까지 재귀호출
    if parent[x] != x:
        return find_parent(parent, parent[x])  
    return x #결국 본인이 루트노드인 최고봉이 있을테니까!

#두 원소가 속한 집합을 합치기(합집합)
def union_parent(parent,a,b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a<b:
        parent[b] = a
    else:
        parent[a] = b

#Union연산 각각 수행
for i in range(e):
    a,b = map(int , input().split())
    union_parent(parent,a,b)

#각 원소가 속한 집합 출력하기
print("각 원소가 속한 집합", end = " ")
for i in range(1,v+1):
    print(find_parent(parent,i), end = " ")
print()

#부모 테이블 내용 출력하기
print("부모 테이블 : ", end = " ")
for i in range(1,v+1):
    print(parent[i], end = " ")

서로소 집합 자료구조의 기본적인 구현 방볍의 문제점

🚀 합집합(Union) 연산이 편향되게 이루어지는 경우 찾기(Find)함수가 비효율적으로 동작한다.

🚀 최악의 경우에는 찾기(Find)함수가 모든 노드를 다 확인하게 되어 시간 복잡도가 O(V)이다.

  • 다음과 같이 {1,2,3,4,5}의 총 5개의 원소가 존재하는 상황을 확인해보자.
  • 수행된 연산들 : 𝑈𝑛𝑖𝑜𝑛(4,5), 𝑈𝑛𝑖𝑜𝑛(3,4), 𝑈𝑛𝑖𝑜𝑛(2,3), 𝑈𝑛𝑖𝑜𝑛(1,2)

서로소 집합 자료구조 : 경로 압축

🚀 찾기(Find) 함수를 최적화하기 위한 방법으로 경로 압축(Path Compression)을 이용할 수 있다.

  • 찾기(Find)함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 바로 갱신한다.
# 특정한 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]
  • 경로 압축 기법을 적용하면 각 노드에 대하여 찾기(Find) 함수를 호출한 이후에 해당 노드의 루트 노드가 바로 부모 노드가 된다

  • 시간 복잡도가 개선된다 !!!



🏈 경로 압축이 적용된 서로소 집합 자료구조 코드

import sys
sys.stdin = open("input.text", "rt")

#노드의 개수와 간선(Union 연산)의 개수 입력받기
v,e = map(int, input().split())
parent = [0] * (v+1)  #부모 테이블 초기화

#부모 테이블상에서 부모를 자기 자신으로 초기화
for i in range(1,v+1):
    parent[i] = i

#특정 원소가 속한 집합을 찾기
def find_parent(parent, x):   #(부모테이블, 노드의 번호) 인자로 들어옴
    #루트노드가 아니라면, 루트노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

#두 원소가 속한 집합을 합치기(합집합)
def union_parent(parent,a,b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a<b:
        parent[b] = a
    else:
        parent[a] = b

#Union연산 각각 수행
for i in range(e):
    a,b = map(int , input().split())
    union_parent(parent,a,b)

#각 원소가 속한 집합 출력하기
print("각 원소가 속한 집합", end = " ")
for i in range(1,v+1):
    print(find_parent(parent,i), end = " ")
print()

#부모 테이블 내용 출력하기
print("부모 테이블 : ", end = " ")
for i in range(1,v+1):
    print(parent[i], end = " ")

🚀 서로소 집합을 활용한 사이클 판별

⚽ 서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다.

  • 참고로 방향 그래프에서의 사이클 여부는 DFS를 이용하여 판별할 수 있다.

⚽ 사이클 판별 알고리즘
1. 각 간선을 하나씩 확인하며 두 노드에 대하여 합집합(Union) 연산을 수행한다.

  • 루트 노드가 서로 다르다면 두 노드에 대하여 합집합(Union) 연산을 수행한다.
  • 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것 !
  1. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복한다.

👻 1번의 과정을 반복해서 모든 간선이 다 처리될 때까지 사이클이 발생하지 않았다면 그래프의 사이클은 없다고 판단할 수 있다.

서로소 집합을 활용한 사이클 판별 코드

Union 연산 정보가 주어질 때, 즉 간선 정보가 주어질 때, 간선 하나하나를 확인하면서 Find 연산을 취해 각 노드의 부모노드를 찾는다. 그리고 찾아낸 2개의 부모 노드들이 같으면 사이클이 있다고 판별할 수 있고 만약 부모 노드들이 같지 않으면 Union 연산을 취해서 부모 자식 간의 노드 관계를 형성한다.

  • 루트노드가 동일하면 사이클이 발생한 것이다 !
import sys
sys.stdin = open("input.text", "rt")

#노드의 개수와 간선(Union 연산)의 개수 입력받기
v,e = map(int, input().split())
parent = [0] * (v+1)  #부모 테이블 초기화

#부모 테이블상에서 부모를 자기 자신으로 초기화
for i in range(1,v+1):
    parent[i] = i

cycle = False #사이클 발생 여부

#특정 원소가 속한 집합을 찾기
def find_parent(parent, x):   #부모테이블, 노드의 번호 인자로 들어옴
    #루트노드가 아니라면, 루트노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

#두 원소가 속한 집합을 합치기(합집합)
def union_parent(parent,a,b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a<b:
        parent[b] = a
    else:
        parent[a] = b

for i in range(e):  #간선의 개수만큼 확인
    a,b = map(int, input().split())
    #사이클이 발생한 경우 종료
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break
    else:  #사이클이 발생하지 않았다면 합집합 연산 수행. (같은 집합으로 만들어줌)
        union_parent(parent, a,b)

if cycle == True:
    print("사이클이 발생")
else:
    print("사이클이 발생하지 않음")

⚽ 문제 유형을 보며 연습

집합의 표현

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

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

입력

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

출력

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

해당 문제 코멘트

전형적인 서로소 집합을 활용하는 문제이다.(대놓고 사용하라고 문제가..) 서로소 집합 자료구조는 합집합 연산과 찾기 연산으로 구성되어 있다.

import sys
sys.stdin = open("input.text", "rt")
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

#유니온 파인드
n,m = map(int, input().split()) #노드, 간선(연산)
#0은 합집합 연산, 1은 찾기 연산
parent = [0] * (n+1)
for i in range(1,n+1):
    parent[i] = i

cycle = False #사이클 발생 여부

#특정 원소가 속한 집합(부모)을 찾기(Find)
def find_parent(x): #현재 노드에 대한 부모 찾기.
    if parent[x] != x:
        parent[x] = find_parent(parent[x])
    return parent[x]

#두 원소가 속한 집합을 합치기(합집합)
def union_parent(a,b): 
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

for _ in range(m):
    oper, a, b = map(int, input().split())
    if oper == 0: #합집합
        union_parent(a,b)
    elif oper == 1:
        if find_parent(a) == find_parent(b):
            print("YES")
        else:
            print("NO")

다른 문제로 활용해보자.

여행 가자

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.

도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.

입력

첫 줄에 도시의 수 N이 주어진다. N은 200이하이다. 둘째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다. M은 1000이하이다. 다음 N개의 줄에는 N개의 정수가 주어진다. i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다. 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다. A와 B가 연결되었으면 B와 A도 연결되어 있다. 마지막 줄에는 여행 계획이 주어진다. 도시의 번호는 1부터 N까지 차례대로 매겨져 있다.

출력

첫 줄에 가능하면 YES 불가능하면 NO를 출력한다.

import sys
sys.stdin = open("input.text", "rt")
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from collections import deque

n = int(input())
m = int(input())
g = [list(map(int, input().split())) for _ in range(n)]
plan = list(map(int ,input().split()))

parent = [0] * (n+1)
for i in range(1,n+1):
    parent[i] = i
def find_parent(x):
    if parent[x] != x:
        parent[x] = find_parent(parent[x])
    return parent[x]

def union_parent(a,b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b: #작은 것이 부모로 설정
        parent[b] = a
    else:
        parent[a] = b
    

for i in range(n):
    for j in range(n):
        if g[i][j] == 1: #연결되어 있다면. 같은 집합으로 분류
            union_parent(i+1,j+1)

v = plan[0]
for i in plan:
    if parent[i] != parent[v]:  #모두 부모가 같아야 하므로 시작노드를 기준으로 판단하면 됨.
        print("NO")
        break
else:
    print("YES")

해당 문제 코멘트

그래프의 모든 간선 정보가 주어졌을 때, 유니온 파인드를 이용해 특정 정점부터 특정 정점까지 이어져 있는지 손쉽게 확인할 수 있다.

즉 이 문제에서처럼 여행 계획이 모두 한 분리 집합 내에 속한다면 YES, 아니라면 NO를 출력할 것이다.

  • 이 문제의 예시처럼 중복이 가능했다. 그렇기에 유니온 파인드를 사용하면 쉽게 풀리는 문제였다. (아직 문제만 보고 어떤 알고리즘을 사용해야 하는가에 대해서는.. 더 풀어봐야겠다.)

👻 BFS, DFS 뿐만 아니라 유니온 파인드(서로소 집합)로도 두 정점이 연결되어 있는지를 확인할 수 있다는 것을 알아두자 !!

  • 이 문제는 dfs, bfs 모두 사용가능했다 ! (둘 다 풀어볼 것 !!)

  • 중요한건 서로소 집합은 무방향 그래프 내에서만 사이클을 판별할 수 있다는 것 !!

⚽ 유니온 파인드는 다른 고급 그래프 알고리즘의 베이스가 된다는 점에서 반드시 익히고 들어가야 한다! 유니온 파인드를 응요한 크루스칼 알고리즘에 대해서도 공부해야 한다.

profile
조현수
back-end, 지속 성장 가능한 개발자를 향하여
이전 포스트

라인 스위핑 알고리즘

0개의 댓글