Union-Find를 쓸 수 있는 문제 유형 5가지

🎯 Union-Find를 떠올려야 하는 신호(패턴)

아래 상황 중 하나라도 보이면 무조건 Union-Find부터 의심해야 해.

---

✔ 1) "합치기(union) / 묶기 / 연결하기 / 같은 그룹"이라는 표현이 나올 때

예:

• 친구 관계(Friend Network)
• SNS 팔로우 묶기
• 같은 팀 만들기
• 섬/영역/구역을 하나로 합치기
• 사람/도형/원소들을 같은 집합으로 묶기

---

✔ 2) 결과가 "그룹 크기" 또는 "연결 요소 개수"일 때

• “현재 속한 네트워크의 인원 출력”
• “몇 개의 영역이 생기는가?”
• “그룹별 개수는?”
• “분리된 구역은?”

---

✔ 3) 서로 겹치거나 닿는 기하학 도형(선분, 원, 직사각형) 문제

이 문제도 여기에 해당됨.

유형 예:

• 원 1억 개 → 겹치는 원들을 하나의 영역으로 묶기
• 직사각형이 맞닿는지 파악하기 → 묶기
• 점/선분이 이어지는지 → 묶기

---

✔ 4) 실시간으로 “두 개의 무언가를 연결하라” → 이후 질의 발생

예:

• A와 B를 같은 집합으로 만들어라
• 이후 X와 Y가 같은 집합인지 물어봄

이런 구조는 90% Union-Find.

---

✔ 5) BFS/DFS로 하면 10^6~10^7 이상 연결 관계가 생겨서 느릴 때

Union-Find는 거의 O(1)로 작동하니 훨씬 적합함.

---

🎯 Union-Find 자주 나오는 대표 문제

유형	예시
친구/네트워크	Friend Network, 집합의 개수
기하학 영역	원/직사각형 접촉 문제
서버/컴퓨터 연결	네트워크 연결 여부, 최소 비용 연결
클러스터링	그룹 묶기, 그룹 수 세기
부모-자식/팀 배정	A와 B는 같은 팀
어떤 조건에 의해 “둘을 연결”	예: 길이 연결되면 같은 구역

 

---

⭐ 앞으로 이런 문제 보면 바로 Union-Find 떠올리기

문제를 보면 딱 두 가지 체크만 하면 된다.

✔ Q1. "두 개의 무언가를 연결해야 하나?"

→ YES면 Union-Find 후보.

✔ Q2. "그룹 크기 / 그룹 개수 / 같은 그룹 여부" 출력인가?

→ 100% Union-Find.

이 두 조건이 동시에 나오면 → 확정이다.