7강: 흩어진 내 편을 찾아라, 유니온 파인드(Union-Find)

5 minute read

7강: 흩어진 내 편을 찾아라, 유니온 파인드(Union-Find)

안녕하세요! 여러분의 코딩 구원투수, 재준봇입니다.

지난 6강에서는 BFS라는 녀석을 가지고 미로 속에서 최단 거리를 찾는 법을 배워봤죠? 그때 다들 “아, 그냥 옆으로 옆으로 계속 가다 보면 결국 나오는구나” 하고 무릎을 탁 치셨을 겁니다. 하지만 세상일이 그렇게 단순하게 길 찾기만으로 해결될까요? 때로는 “얘랑 얘랑 같은 팀이야?”, “우리가 같은 그룹에 속해 있나?” 같은 관계의 문제를 풀어야 할 때가 옵니다.

오늘은 바로 그런 상황에서 빛을 발하는 유니온 파인드 알고리즘을 가져왔습니다. 이름부터가 뭔가 합치고(Union) 찾는(Find) 느낌이 팍 오지 않나요? 코딩 초보자분들도 단번에 이해하실 수 있게 제가 아주 찰떡같은 비유로 설명해 드릴 테니 끝까지 따라오세요. 이거 모르면 나중에 네트워크 문제나 그룹핑 문제 만났을 때 진짜 멘붕 옵니다!

유니온 파인드, 도대체 정체가 뭐야?

쉽게 생각해서 유니온 파인드는 “족보 찾기” 혹은 “파벌 관리”라고 보시면 됩니다.

여러분이 아주 복잡한 중학교 교실에 있다고 상상해 보세요. 여기저기 끼리끼리 뭉쳐서 무리가 형성되어 있습니다. 이때 우리가 궁금한 건 딱 두 가지입니다.

유니온(Union): “철수랑 영희가 이제부터 같은 팀이 됐대!” (두 그룹을 하나로 합치기)
파인드(Find): “민수랑 지수는 같은 팀인가?” (두 사람이 같은 대표자를 공유하는지 확인하기)

여기서 핵심은 각 팀마다 딱 한 명의 대표(대장)를 정하는 것입니다. 내가 누구 팀인지 궁금하면 내 위에 대장이 누구인지 물어보고, 그 대장의 대장을 물어보고, 결국 최종 보스(루트 노드)가 누구인지 찾아내는 방식이죠. 만약 두 사람의 최종 보스가 같다면? 네, 두 사람은 같은 팀인 겁니다.

왜 그냥 리스트에 저장 안 하고 이걸 쓰나요?

초보자 폭풍 질문! “재준봇님, 그냥 리스트나 딕셔너리에 ‘철수: A팀, 영희: A팀’ 이렇게 저장하면 되는 거 아닌가요? 굳이 복잡하게 대장을 찾고 합치고 해야 하나요?”

아주 날카로운 질문입니다! 하지만 데이터가 10명, 20명이 아니라 100만 명이라고 생각해보세요. A팀과 B팀이 합쳐졌을 때, 리스트 방식을 쓰면 A팀에 속한 50만 명의 이름을 일일이 다 수정해서 B팀으로 바꿔줘야 합니다. 여기서 시간이 다 가버리죠.

하지만 유니온 파인드는 A팀의 대장과 B팀의 대장, 딱 두 사람만 연결해주면 끝납니다. “이제부터 A팀 대장은 B팀 대장 밑으로 들어가!”라고 명령 한 번만 내리면 50만 명의 소속이 한 번에 바뀌는 마법이 일어나는 것이죠. 효율성이 정말 압도적입니다.

시간 복잡도: 얼마나 빠른가요?

이 알고리즘의 진짜 무서운 점은 경로 압축(Path Compression)이라는 기술을 썼을 때입니다. 대장을 찾으러 올라가는 길에 “아, 내 최종 보스는 이 사람이구나!”라고 기억해두는 방식인데요. 이렇게 하면 거의 상수에 가까운 시간, 즉 O(alpha(N))라는 말도 안 되게 빠른 속도로 동작합니다. 여기서 alpha는 아커만 함수의 역함수인데, 사실상 무한대에 가까운 데이터가 아니면 그냥 1이라고 생각해도 무방할 정도로 빠릅니다.

오늘의 실전 문제: “학교 내 비밀 동아리 파악하기”

자, 이제 이론은 끝났습니다. 바로 실전에 투입해 보죠. 상황은 다음과 같습니다.

[문제 상황] 당신은 학교의 학생회장입니다. 학생들은 자기들끼리 비밀리에 동아리를 만들고 있습니다. 그런데 누가 어느 동아리인지 명단이 없습니다. 오직 “A와 B가 같은 동아리다”라는 정보만 계속해서 들어옵니다.

여러분은 다음의 정보들을 처리해야 합니다.

두 학생이 같은 동아리라는 정보가 들어오면 두 그룹을 합칩니다.
특정 두 학생을 지목했을 때, 이들이 현재 같은 동아리 소속인지 확인하여 “YES” 또는 “NO”를 출력해야 합니다.

[입력 예시]

1 2 (1번과 2번이 같은 팀)
2 3 (2번과 3번이 같은 팀)
4 5 (4번과 5번이 같은 팀)
질문: 1번과 3번은 같은 팀인가? -> 결과: YES
질문: 1번과 4번은 같은 팀인가? -> 결과: NO

이 문제를 어떻게 설계하고 코드로 구현할지 이제 공개하겠습니다.

해결 방안 및 정답 코드 보기 (클릭)

해결 방안 가이드 (알고리즘 설계)

이 문제는 전형적인 유니온 파인드 구조로 풀 수 있습니다.

부모 배열(Parent Array) 생성: 처음에는 모든 학생이 각자 자기 자신이 대장인 상태로 시작합니다. parent[i] = i 형태로 초기화합니다.
Find 함수 구현: 특정 학생의 최종 보스를 찾는 함수입니다. 재귀적으로 parent[parent[i]]를 찾아 올라가며, 찾은 최종 보스를 바로 내 부모로 설정하는 ‘경로 압축’을 적용해 속도를 높입니다.
Union 함수 구현: 두 학생의 최종 보스를 각각 찾습니다. 만약 보스가 다르다면, 한쪽 보스의 부모를 다른 쪽 보스로 설정하여 두 그룹을 하나로 합칩니다.
판별: 두 학생의 Find 결과값이 같으면 같은 팀, 다르면 다른 팀입니다.

파이썬 정답 코드 및 상세 해설

import sys

# 입력을 빠르게 받기 위한 설정입니다.
input = sys.stdin.readline

def find(parent, x):
    # x의 부모가 자기 자신이라면, x가 바로 최종 보스입니다.
    if parent[x] == x:
        return x
    
    # 경로 압축(Path Compression) 핵심 구간!
    # 재귀적으로 최종 보스를 찾고, 그 결과를 parent[x]에 바로 저장합니다.
    # 이렇게 하면 다음에 찾을 때는 한 번에 보스에게 갈 수 있습니다.
    parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, a, b):
    # a와 b의 최종 보스를 각각 찾습니다.
    rootA = find(parent, a)
    rootB = find(parent, b)
    
    # 두 보스가 다르다면, 한 팀으로 합칩니다.
    if rootA != rootB:
        # 여기서는 단순하게 rootA의 보스를 rootB로 설정합니다.
        parent[rootA] = rootB
        return True # 합치기 성공
    return False # 이미 같은 팀임

# 메인 실행부
def solve():
    # 학생 수와 연산 수 입력 (예: 학생 10명, 연산 5번)
    # 실제 코테에서는 입력 형식이 정해져 있겠지만 여기선 예시로 작성합니다.
    n = 10 
    parent = [i for i in range(n + 1)] # 1번부터 n번까지 인덱스를 사용하기 위해 n+1 생성
    
    # 가상의 입력 데이터 (학생A, 학생B)
    connections = [
        (1, 2),
        (2, 3),
        (4, 5)
    ]
    
    # 관계 형성 (Union 단계)
    for a, b in connections:
        union(parent, a, b)
        print(f"{a}번과 {b}번이 이제 같은 동아리입니다.")

    # 확인 단계 (Find 단계)
    test_cases = [(1, 3), (1, 4)]
    for u, v in test_cases:
        if find(parent, u) == find(parent, v):
            print(f"결과: {u}번과 {v}번은 같은 팀인가요? -> YES")
        else:
            print(f"결과: {u}번과 {v}번은 같은 팀인가요? -> NO")

if __name__ == "__main__":
    solve()

코드 상세 해설:

parent = [i for i in range(n + 1)]: 모든 학생이 처음에 각자의 대장인 상태를 만듭니다. (자기 자신을 가리킴)
parent[x] = find(parent, parent[x]): 이 한 줄이 유니온 파인드의 꽃입니다. 루트 노드까지 올라갔다 내려오면서 거치는 모든 노드들의 부모를 루트 노드로 직접 연결해버립니다. 다음에 find를 호출할 때는 단 한 번만에 보스를 찾게 됩니다.
union(parent, a, b): 두 명의 보스를 찾아 서로 연결함으로써 두 거대 집단을 하나로 묶어버리는 과정입니다.

한계점 및 실무 개선점

실무에서 이 알고리즘을 그대로 사용할 때 주의해야 할 점이 몇 가지 있습니다.

재귀 깊이 제한 (Recursion Limit): 파이썬은 기본적으로 재귀 호출 횟수에 제한이 있습니다. 데이터가 수만 개 이상으로 많아지면 RecursionError가 발생할 수 있습니다. 이 경우 sys.setrecursionlimit()를 통해 제한을 늘려주거나, 반복문을 이용한 find 함수로 구현해야 합니다.
Union by Rank: 위 코드에서는 단순히 한쪽을 다른 쪽에 붙였습니다. 하지만 트리의 높이가 너무 길어지면 효율이 떨어질 수 있습니다. 따라서 트리의 높이(Rank)를 저장해두었다가, 높이가 낮은 트리를 높은 트리 밑에 붙이는 ‘Union by Rank’ 기법을 사용하면 성능을 극한으로 끌어올릴 수 있습니다.
동적 데이터 처리: 실제 서비스에서는 사용자가 실시간으로 그룹에 가입하거나 탈퇴할 수 있습니다. 유니온 파인드는 ‘합치기’는 매우 빠르지만, 특정 요소를 그룹에서 ‘제거’하는 기능은 구현하기 매우 까다롭습니다. 제거 기능이 필요하다면 다른 자료구조를 고민해야 합니다.

</s flesh>

<hr>

💬 궁금한 점이 있다면 자유롭게 댓글을 남겨주세요! (AI 비서가 답변해 드립니다 🤖)

Twitter Facebook LinkedIn