[Algorithm] 이분 매칭 (Bipartite Matching)

이분 매칭

• A 집단이 B 집단을 선탁하는 방법에 대한 알고리즘
• 즉, 2개의 정점 그룹이 있을 때, 그룹에서 그룹으로 정점의 최대 매칭을 찾는 알고리즘이다.

 

위와 같은 두 그룹의 정점이 있을 때 각 그룹을 연결할 수 있는 간선의 정보는 아래와 같다.

A : 2, 5
B : 2, 3, 4
C : 1, 5
D: 1, 2, 5
E : 2

• 이 정보를 가지고 정점을 한 번만 사용해서 최대한 많은 정점이 매칭되게 해보자.
• DFS와 visted 배열을 활용하여 구해준다. 

우선 A가 매칭가능한 번호 중 빠른 번호인 2를 매칭 시켜준다.

 

• 이후 B를 매칭 시켜주는데 B가 연결할 수 있는 가장 빠른 번호도 2이므로
• A로 돌아가 매칭 시킬 수 있는 다른 정점이 있는지 살펴본 후 존재한다면 A가 양보해준다.
• 따라서, A - 5, B - 2와 매칭이 된다.

• 다음 C를 매칭 시켜주는데 바로 1과 매칭 시켜줄 수 있다.
• D를 매칭시키기 위하여 보니까 1과 매칭을 시켜주려니 이미 C가 1과 짝이기 때문에
• B의 케이스와 마찬가지로 C로 돌아가서 새로 매칭을 시켜주려고 한다.
• 근데 이 때, C가 매칭할 수 있는 다른 정점은 5번인데, 5번은 이미 A와 매칭이 되어있고
  • A의 경우, 2번으로 돌아가려니 B가 매칭이 되어있다.
  • 다시 B로 돌아가 B를 3번으로 매칭하니 아래와 같이
  • A - 2, B - 3, C - 5, D - 1로 매칭이 가능해졌다.

• 남은 정점은 E번이므로 매칭을 해보려하지만 2번은 이미 A가 연결되어있고, A가 양보할 수 있는 정점이 없다.
• 따라서, 최대 매칭 수는 4가 된다.
• 아래는 DFS와 VISITED를 활용한 이분 매칭 알고리즘의 예시이다!
  • 시간 복잡도는 O(V*E)이 된다.
  • 양 쪽 정점의 개수를 서로 곱한 값
  • 네트워크 플로우 -> 에드몬드 카프 알고리즘보다 월등히 빠르게 사용 가능하다.

 

# 현재 매칭을 시작할 번호를 인자로 받는다
def bipartite_matching(num):
    # 매칭이 가능한 번호를 순회
    for idx in alpha[num]:
        # 만약 방문하지 않았다면 매칭 시작
        if not visited[idx]:
            visited[idx] = True
            # 매칭하려는 정점에 다른 수가 배정되어 있지 않거나
            # 매칭되있는 수를 다른 정점에 배치 가능하다면
            if connect[idx] == -1 or bipartite_matching(connect[idx]):
                connect[idx] = num
                return 1

    return 0


# 그룹 2개
# A, B, C, D, E 를 인덱스 0 1 2 3 4 로 사용
alpha = [[2, 5], [2, 3, 4], [1, 5], [1, 2, 5], [2]]

# 전체 매칭 수를 기록할 배열
connect = [-1] * 6
for i in range(5):
    # 현재 매칭하며 방문했는지 표시
    visited = [False] * 6
    bipartite_matching(i)

print(connect)

# =============
# [-1, 3, 0, 1, -1, 2]