2026-02-03 | 6 min read | 127 | 그래프 이분 매칭 알고리즘

6-10. 그래프: 이분 매칭

1. 이분 매칭의 이해

그래프 이론은 다양한 현실 문제를 모델링하고 해결하는 데 유용한 도구입니다. 그중에서도 이분 매칭(Bipartite Matching)은 두 개의 분리된 그룹 간의 관계를 효율적으로 표현하고 분석하는 데 사용되는 중요한 개념입니다. 이분 매칭은 특정한 조건을 만족하는 그래프, 즉 이분 그래프(Bipartite Graph)에서 최대 매칭(Maximum Matching)을 찾는 알고리즘을 의미합니다.

1) 이분 그래프란?

이분 그래프는 그래프의 정점(Vertex, Node)들을 두 개의 독립적인 집합으로 나눌 수 있는 그래프를 말합니다. 이 두 집합을 보통 X와 Y로 표기하며, 그래프의 모든 간선(Edge)은 X의 정점과 Y의 정점을 연결합니다. 다시 말해, X 내의 정점끼리, Y 내의 정점끼리는 연결되지 않습니다.

이분 그래프 설명 뒤

위 그림은 이분 그래프의 전형적인 형태를 보여줍니다. X 집합과 Y 집합, 두 개의 그룹으로 나뉘어져 있으며, 각 그룹 내의 노드들은 서로 연결되어 있지 않고, X의 노드와 Y의 노드 사이에서만 연결이 이루어집니다.

2) 매칭이란?

그래프에서 매칭(Matching)이란, 그래프의 간선들의 부분 집합으로, 이 부분 집합에 속한 간선들은 서로 공통된 정점을 공유하지 않습니다. 즉, 각 정점은 최대 한 개의 매칭된 간선에만 포함될 수 있습니다.

3) 최대 매칭

최대 매칭(Maximum Matching)은 주어진 그래프에서 가능한 가장 많은 수의 간선을 포함하는 매칭을 찾는 것을 의미합니다. 이분 매칭 알고리즘은 이러한 최대 매칭을 효율적으로 찾아내는 데 목적을 둡니다.

2. 이분 매칭 문제의 예시

이분 매칭 문제는 다양한 현실 문제를 모델링하는 데 사용될 수 있습니다. 다음은 그 예시입니다.

구인-구직 문제: 구직자 집합 X와 직업 집합 Y가 주어졌을 때, 각 구직자가 특정 직업에 적합한 정도(매칭의 가중치)를 고려하여 최대 인원을 채용하는 문제.
작업 할당 문제: 작업 집합 X와 작업자 집합 Y가 주어졌을 때, 각 작업자가 특정 작업을 얼마나 잘 수행하는지 고려하여 모든 작업을 가장 효율적으로 할당하는 문제.
결혼 문제: 남성 집합 X와 여성 집합 Y가 주어졌을 때, 각 남성이 특정 여성과 맺어질 수 있는 가능성(선호도)을 고려하여 최대한 많은 커플을 매칭하는 문제.

이러한 문제들은 모두 두 그룹 간의 관계를 분석하고, 최적의 조합을 찾는다는 공통점을 가지고 있습니다.

3. Hopcroft-Karp 알고리즘: 효율적인 이분 매칭

이분 그래프에서 최대 매칭을 찾는 가장 효율적인 알고리즘 중 하나는 Hopcroft-Karp 알고리즘입니다. 이 알고리즘은 O(√V * E)의 시간 복잡도를 가지며, 여기서 V는 정점의 수, E는 간선의 수입니다. 이는 다른 알고리즘에 비해 상당히 빠른 속도를 보여줍니다.

1) 알고리즘 개요

Hopcroft-Karp 알고리즘은 증가 경로(Augmenting Path)를 사용하여 최대 매칭을 찾아냅니다. 증가 경로는 현재 매칭에 포함되지 않은 간선을 추가하여 매칭의 크기를 1 증가시킬 수 있는 경로를 의미합니다. 알고리즘은 다음과 같은 단계를 반복합니다.

너비 우선 탐색(BFS): BFS를 사용하여 현재 매칭 상태에서 가장 짧은 증가 경로들을 찾습니다.
깊이 우선 탐색(DFS): DFS를 사용하여 찾은 증가 경로들을 따라 매칭을 수행합니다.
반복: 증가 경로가 더 이상 없을 때까지 1, 2단계를 반복합니다.

2) 증가 경로 찾기 (BFS)

BFS는 각 노드에 레벨을 할당하여 증가 경로를 찾는 데 사용됩니다.

레벨 0: 매칭되지 않은 X 집합의 노드들.
레벨 i: 레벨 i-1의 노드와 매칭된 Y 집합의 노드와 연결된 X 집합의 노드.

BFS는 증가 경로의 길이를 최소화하여, 매칭을 효율적으로 증가시킵니다.

3) 매칭 수행 (DFS)

DFS는 BFS에서 찾은 증가 경로를 따라 실제 매칭을 수행합니다. DFS는 각 노드에 대해 다음을 수행합니다.

매칭되지 않은 노드를 찾으면 매칭을 수행하고, 경로를 따라 역추적합니다.
매칭된 노드를 만나면, 해당 매칭을 해제하고 다른 경로를 탐색합니다.

4) 알고리즘 흐름

알고리즘의 전체 흐름을 그림으로 나타내면 다음과 같습니다.

Hopcroft-Karp 알고리즘 흐름 설명 뒤

위 그림은 Hopcroft-Karp 알고리즘의 전체적인 흐름을 시각적으로 보여줍니다. BFS와 DFS의 상호작용을 통해 증가 경로를 찾고, 매칭을 갱신하는 과정을 명확하게 나타냅니다.

4. Hopcroft-Karp 알고리즘 구현 (Python)

def hopcroft_karp(graph):
    """
    Hopcroft-Karp 알고리즘을 사용하여 이분 그래프의 최대 매칭을 찾습니다.

    Args:
        graph: 이분 그래프를 인접 리스트로 표현한 딕셔너리.
               키는 X 집합의 노드, 값은 해당 노드와 연결된 Y 집합의 노드 리스트.

    Returns:
        최대 매칭의 크기.
    """
    X = list(graph.keys())
    Y = set()
    for x in X:
        Y.update(graph[x])
    Y = list(Y)

    match = {}  # Y 집합의 노드가 X 집합의 어떤 노드와 매칭되었는지 저장
    for y in Y:
        match[y] = None

    def bfs():
        """
        BFS를 사용하여 증가 경로를 찾습니다.
        """
        distance = {}  # 각 노드의 거리를 저장
        for x in X:
            distance[x] = float('inf')
        for y in Y:
            distance[y] = float('inf')

        queue = []
        for x in X:
            if all(match[y] != x for y in graph[x]):  # 매칭되지 않은 X 노드
                distance[x] = 0
                queue.append(x)

        while queue:
            u = queue.pop(0)
            if u in X:  # X 집합의 노드
                for v in graph[u]:
                    if distance[v] == float('inf'):
                        distance[v] = distance[u] + 1
                        queue.append(v)
            else:  # Y 집합의 노드
                if match[u] is not None and distance[match[u]] == float('inf'):
                    distance[match[u]] = distance[u] + 1
                    queue.append(match[u])

        return distance

    def dfs(u, distance):
        """
        DFS를 사용하여 증가 경로를 따라 매칭을 수행합니다.
        """
        if u not in X:
            return False

        for v in graph[u]:
            if distance[v] == distance[u] + 1 and (match[v] is None or dfs(match[v], distance)):
                match[v] = u
                return True
        return False

    max_matching = 0
    while True:
        distance = bfs()
        if all(distance[x] == float('inf') for x in X):
            break
        for x in X:
            if all(match[y] != x for y in graph[x]):  # 매칭되지 않은 X 노드
                if dfs(x, distance):
                    max_matching += 1

    return max_matching

1) 코드 해설

hopcroft_karp(graph) 함수는 입력으로 이분 그래프를 인접 리스트 형태로 받습니다.
match 딕셔너리는 Y 집합의 각 노드에 매칭된 X 집합의 노드를 저장합니다.
bfs() 함수는 BFS를 사용하여 증가 경로를 찾고, 각 노드의 거리를 계산합니다.
dfs(u, distance) 함수는 DFS를 사용하여 증가 경로를 따라 매칭을 수행합니다.
max_matching 변수는 최대 매칭의 크기를 저장하고, 알고리즘이 종료될 때 반환됩니다.

2) 사용 예시

# 예시 그래프 (인접 리스트)
graph = {
    'A': ['x', 'y'],
    'B': ['y'],
    'C': ['x', 'z']
}

result = hopcroft_karp(graph)
print(f"최대 매칭 크기: {result}")  # 출력: 최대 매칭 크기: 2

5. 알고리즘의 응용 및 확장

Hopcroft-Karp 알고리즘은 다양한 분야에서 활용될 수 있으며, 문제의 특성에 따라 여러 가지 방식으로 확장될 수 있습니다.

1) 실용적인 활용 예시

작업 스케줄링: 여러 작업자가 여러 작업을 수행해야 할 때, 각 작업자가 특정 작업을 수행하는 데 걸리는 시간이나 비용을 고려하여 최적의 작업 할당을 찾는 데 사용될 수 있습니다.
네트워크 라우팅: 네트워크에서 특정 노드 간의 최대 대역폭을 가진 경로를 찾는 데 사용될 수 있습니다.
데이터 마이닝: 데이터베이스에서 특정 조건에 맞는 항목들을 연결하여 정보를 추출하는 데 활용될 수 있습니다.

2) 알고리즘의 변형 및 확장

가중치가 있는 이분 매칭: 간선에 가중치가 부여된 경우, 최대 가중치 매칭(Maximum Weighted Matching)을 찾는 알고리즘으로 확장될 수 있습니다 (예: Hungarian Algorithm).
안정 결혼 문제: 특정 선호도를 기반으로 매칭을 찾는 문제 (예: Gale-Shapley 알고리즘).