🌱 알면 도움되는 코딩 테스트 유형: 8) #Disjoint_Set

• 이번에는 자주 사용되지는 않지만, 알아두면 좋을 법한 유형 중 하나인 분리 집합(Disjoint Set)에 대해 이야기해보려고 해요.
• 분리 집합은 원소들을 서로 중복되지 않게 여러 개의 집합으로 나누고, 각각의 집합들에 대해 합집합(union)과 찾는(find) 연산을 수행하는 자료구조입니다.
• 이 글에서는 분리 집합의 개념과 코딩 테스트에서 분리 집합 문제를 접하게 되었을 때, 어떻게 접근해야 하는지에 대해 간단히 알아보도록 하죠.

 

✨ 분리 집합의 개념

• 분리 집합은 서로 중복되지 않는 부분 집합들로 나누어진 원소들의 데이터 구조입니다. 각각의 부분 집합은 대표 원소를 가지며, 같은 부분 집합에 속한 원소들은 같은 대표 원소를 공유해요. (당연한 얘기죠.)
• 예를 들어서 {1, 2, 3}과 {4, 5}라는 두 개의 부분 집합이 있다고 가정해보도록 하죠. 이때, 각각의 부분 집합에서 예를 들어 하나씩 대표 원소를 선택하게 되면, {1}과 {4}를 뽑는 경우가 있겠죠.
• 만약 원소 2와 3을 {1}에 합치고 싶다면, 분리 집합에서는 각각의 대표 원소가 다른 것을 먼저 확인하고 합칠 수가 있게 됩니다.
• 주요 연산은 아래 3가지가 있어요.
  • MakeSet(x): 원소 x를 포함하는 새로운 집합을 생성
  • Find(x): 원소 x가 속한 집합(루트)을 찾아 반환
  • Union(x, y): x와 y가 속한 두 개의 집합을 병합
• 분리 집합은 주로 그래프 알고리즘에서 활용되고, 상호 배타적인 그룹이나 연결 요소를 관리할 때 유용하게 쓰인답니다.

 

---

✨ 그럼 어떻게 접근하면 좋을까?

• 코딩 테스트에서는 분리 집합 문제가 다양한 방식으로 출제가 됩니다. 일반적으로는 다음과 같이 접근하는데요.

1. 초기화: 문제에서 주어진 조건에 따라 초기 상태를 설정해줘요. 일반적으로 각각의 원소는 자기 자신을 대표로 설정해서 초기화합니다.
2. Union 연산: Union 연산(두 개의 부분 집합을 합치는 연산)이 필요한 경우에는 해당 연산을 수행해줍니다. 예를 들면, A와 B라는 두 개의 부분 집합이 주어진다면 A와 B 중 하나만 선택하여 다른 하나와 Union 연산을 수행하는 식이죠.
3. Find 연산: Find 연산(원소가 속한 부모(대표) 찾기)이 필요한 경우에는 해당 연산을 수행해서 얘가 어떤 부모(대표)에 속하는 자식인지 확인해줍니다.
4. 문제 해결: 문제에서 요구하는 결과를 확인하기 위해 필요한 추가적인 작업을 수행합니다. 예를 들면, 모든 Union 연산 후 최종적으로 남아 있는 서로 다른 부분 집합의 개수 등을 계산하는 적용 방법도 있겠습니다.

 

💡 대표 문제 1. 집합의 표현

1717번: 집합의 표현

 

문제

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

 

해결 방법

• 이 문제는 대표적으로 기본적인 Union-Find(분리 집합) 알고리즘을 사용해서 해결할 수 있죠! 먼저 각 원소가 속한 부모를 찾기 위해서 find 함수를 정의하고, 두 원소가 같은 부모를 가지도록 union 함수를 정의합니다.

import sys; input=sys.stdin.readline; sys.setrecursionlimit(10**6)

def find(x):
    # x의 부모가 x라면, x를 반환
    if parent[x] == x: 
        return x
    # 그게 아니면,
    else:
        # 부모를 재귀적으로 찾고,
        p = find(parent[x])
        parent[x] = p
        # 그 부모를 반환
        return parent[x]

def union(x, y):
    # 각자의 부모 찾기
    x = find(x)
    y = find(y)
    
    # 부모가 같지 않으면 병합할 수 있음!
    if x != y:
        # y의 부모를 x로 설정 (반대로도 가능)
        parent[y] = x

n, m = map(int, input().split())
parent = list(range(n+1))

for _ in range(m):
    op, a, b = map(int, input().split())
    if op == 0: 
        union(a, b)
    elif op == 1:
        if find(a) == find(b): 
            print('YES')
        else: 
            print('NO')

 

💡 대표 문제 2. 여행 가자

1976번: 여행 가자

 

문제

• 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 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라는 여행경로를 통해 목적을 달성할 수 있다.
• 도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.

 

해결 방법

• 이 문제는 여러 도시들 사이의 연결 정보가 주어졌을 때, 주어진 여행 경로가 가능한지를 판단하는 문제죠.
• 분리 집합을 활용하면 각 도시들이 같은 집합에 속해 있는지 쉽게 확인할 수 있게 됩니다.

import sys; input=sys.stdin.readline

def find(x):
    if parent[x] == x: 
        return x
    else:
        p = find(parent[x])
        parent[x] = p
        return parent[x]

def union(x, y):
    x = find(x)
    y = find(y)

    if x != y: 
        parent[y] = x

n = int(input())
m = int(input())

parent = [i for i in range(n+1)]

for i in range(1, n+1):
    data = list(map(int, input().split()))
    
    for j in range(1, len(data)+1):
        if data[j-1] == 1:
            union(i, j)

plan = list(map(int, input().split()))
result = set([find(city) for city in plan])

if len(result) == 1: 
    print('YES')
else: 
    print('NO')

• 각 도시 간 연결 정보를 입력받아 해당 도시들이 같은 부분집합에 속하도록 합니다.
• 그 다음으로 여행 계획에 포함된 모든 도시들이 같은 부분집합에 속해 있는지 확인하고 그 결과를 출력합니다.

위 문제들에서도 볼 수 있듯, 분리 집합은 여러 요소들 간의 연결 관계를 표현하고 활용하는 문제에서 매우 유용할 수 있습니다.