Union-Find 알고리즘

김펭귄·2026년 5월 31일

Today What I Learned (TIL)

목록 보기

140/141

유니온 파인드 (Union-Find) / 서로소 집합 (Disjoint-Set)

알고리즘 문제 풀이(PS)를 하다 보면, "여러 개의 원소들이 있을 때, 얘네가 결국 같은 무리(집합)에 속해 있는지" 효율적으로 판별하고 합쳐야 하는 상황이 자주 발생합니다. 이때 사용하는 최적의 자료구조가 바로 유니온 파인드입니다.

1. 유니온 파인드(Union-Find)란?

이름 그대로 딱 두 가지 연산을 지원하는 자료구조입니다.

Union (합치기): 두 원소가 속한 집합을 하나의 집합으로 합치는 연산
Find (찾기): 어떤 원소가 주어졌을 때, 이 원소가 어느 집합에 속해 있는지(최종 대표자/루트 노드가 누구인지) 찾는 연산. 이를 통해 두 원소가 같은 집합에 속해 있는지 판별할 수 있습니다.

💡 직관적인 비유: '조직도' 만들기

초기 상태: 모든 사람이 각각 독립된 1인 기업(원소)의 대장입니다.
Union(A, B): "A 무리와 B 무리가 합병합니다. 이제부터 대장은 A 무리의 대장으로 통일합니다"

Find(X): "X 사원, 당신 무리의 최고 CEO(최상위 루트)는 누구입니까?"

2. 트리 구조와 부모 배열 구현 원리

컴퓨터에게 무리의 대표자를 효율적으로 알려주기 위해 트리(Tree) 구조와 각 노드의 부모를 기록하는 배열(Parent)을 사용합니다.
임의 접근과 캐시 친화적인 배열을 주로 사용하나, 데이터가 너무 많아지거나 배열인덱스를 만들기 어려울 경우(숫자가 아니라 "Bob"처럼 사람 이름일 경우) unordered_map을 대신 사용

유니온 파인드는 일반적인 트리와 다르게 자식이 부모를 가리키며 거슬러 올라가는 형태를 가집니다.

① 초기화 (Initialization)

처음에는 아무도 연결되어 있지 않으므로, 모든 원소의 부모는 자기 자신입니다.

Parent[i] = i

② Find 연산 (Find Representative)

자신의 부모를 타고 계속 위로 올라가서 Parent[x] == x인 최종 대장(루트 노드)을 찾아 반환합니다.

③ Union 연산 (Merge Sets)

두 원소를 단순히 연결하는 것이 아니라, 두 원소가 속한 무리의 '최고 대장'을 찾아서 한쪽 대장을 다른 쪽 대장 밑으로 편입시켜야 합니다.

3. 핵심 최적화: 경로 압축 (Path Compression)

단순히 부모를 타고 올라가도록 구현하면, 데이터가 순서대로 들어올 때 트리가 한쪽으로 길게 늘어지는 연결 리스트 형태(최악의 경우 $O(N)$ )가 될 수 있습니다.

이를 해결하는 치트키가 바로 경로 압축(Path Compression)입니다.

⚡ 원리

Find 함수가 실행되어 최종 대장을 찾으러 올라가는 길에, 거쳐간 모든 노드들이 최종 대장을 직접 가리키도록 부모 배열을 갱신해 버립니다.

// 경로 압축이 적용된 Find 함수
int Find(int x)
{
    if (Parent[x] == x) return x; // 내가 최종 보스면 나를 반환
    
    // 최종 보스를 찾음과 동시에 내 부모 자리에 바로 꽂아버림!
    return Parent[x] = Find(Parent[x]); 
}

4. 예시문제

백준 1717번 '집합의 표현'

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

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

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

출력
1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

백준 4195번: 친구 네트워크

문제
민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 
우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 
두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 
각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 
다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 
친구 관계는 두 사용자의 아이디로 이루어져 있으며, 
알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력
친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

백준 10775번 - 공항

문제
오늘은 신승원의 생일이다.
박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.
공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.
공항에는 P개의 비행기가 순서대로 도착할 예정이며, 
당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 
비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.
신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 
승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력
첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.
두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.
이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

출력
승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.