부캠 글쓰기 모임 3회

작성일 | In , |

이분 매칭(Bipartite Matching)

이번 글쓰기 주제는 알고리즘입니다. 아이패드 프로 5세대 12.9인치 XDR 디스플레이를 산 기념으로 직접 그림을 그려가며 설명해보도록 하겠습니다.

이분 매칭 알고리즘을 공부하기 전에 먼저 이분 그래프가 무엇인지 알아야 합니다. 위키백과 같은 데서 검색해보면 설명이 다소 어렵게 되어 있는데, 간단히 설명하자면 서로 연결된 정점을 서로 다른 색으로 칠했을 때 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프입니다. 즉, 정점을 두 개의 그룹으로 나누었을 때 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 그래프를 의미합니다. 이산수학 수업 때 분명 배운 내용이지만 저도 기억이 가물가물하네요.

그리고 이분 그래프의 A그룹의 정점(노드) 하나가 B그룹의 정점 하나씩만 가지도록 연결한다면 이분 매칭이라고 할 수 있습니다. 이분 매칭은 기준이 되는 그룹과 상대 그룹을 최대한 많이 연결시켜야 하는 문제를 해결할 수 있습니다. 그래서 일반적으로 이분 매칭 알고리즘 문제는 어떤 그룹에 속한 각각의 구성원들의 매칭이 되길 원하는 상대 그룹 구성원 후보들이 주어졌을 때 최대한 많이 매칭이 이루어질 수 있게 하는 문제입니다. e.g) 회사의 각 직원마다 희망하는 업무 목록이 주어졌을 때, 한 사람 당 업무 하나씩 최대한 많이 매칭시키기.

이분 매칭 알고리즘 흐름

다음과 같이 그래프가 있습니다.

먼저 a1이 희망하는 B그룹의 노드 중 첫 번째인 b1을 a1-b1으로 맺어주도록 합시다. 그러면 그래프의 상태는 아래와 같이 됩니다.

이제 a2가 희망하는 B그룹의 정점과 이어줘야 하는데, 이런…a2의 희망 노드 중 첫 번째가 이미 매칭되어진 b1이군요. 이런 상황에서 이분 매칭의 규칙은 다음과 같습니다.

  1. 매칭되고 싶은 상대 노드가 아직 다른 노드랑 매칭되지 않은 상태라면 그대로 매칭시켜준다.
  2. 매칭되고 싶은 상대 노드가 이미 매칭된 상태라면,
    1. 상대 노드랑 매칭된 노드를 살펴본다. 예를 들어 위 상황에서의 b1은 이미 a1이랑 연결되어 있는데, a1이 희망하는 다른 선택지가 아직 매칭되지 않은 상태라면 그 상대랑 새로 매칭시킨다(a1-b3). 그리고 b1은 a2랑 매칭시킨다.
    2. 2-1의 상황이 불가하다면, a2가 다른 선택지로 물러나거나 혹은 매칭을 하지 못한다.

따라서 룰에 따라 그래프의 상황은 아래와 같이 될 것입니다.

그리고 마지막은 조금 복잡하지만, 앞서 설명한 규칙에 따라 움직인다면 아래와 같은 최종 상태의 그래프를 얻을 수 있습니다.

a4를 b3를 연결하려니, b3가 이미 매칭되어 있기에 b3와 매칭되어 있는 a1이 다른 데로 갈 수 있는지(b1) 알아보고, 그 다른 데랑 이미 매칭된 a2가 또 다른 데로 갈 수 있는지 알아보는… 이러한 작업이 진행된 결과입니다. 잘 모르겠다면 아래의 백준 문제 풀이를 보시고 이해하면 되겠습니다.

방금 사례에서는 총 여덟 개의 노드가 서로 하나씩 짝을 찾아서 다 연결된 케이스입니다. 이제부터 백준에서 이분 매칭 알고리즘으로 풀 수 있는 문제를 찾아 풀어봅시다.

이분 매칭 알고리즘 문제 목록 링크

지금부터 이분 매칭 기본 문제를 풀어보도록 하겠습니다. 글을 읽으시면서 차근차근 이해하시고 문제를 함께 풀 수 있도록 최대한 쉽게 설명하겠습니다. 사실 간단한 DFS 구조입니다.


축사 배정

테스트 케이스 입력 조건이 제시하는대로 그래프를 그려봅시다. 소한테 물어보니까

  • 1번 소 : 2, 5
  • 2번 소 : 2, 3, 4
  • 3번 소 : 1, 5
  • 4번 소 : 1, 2, 5
  • 5번 소 : 2

위와 같이 희망 축사에 대해 응답했습니다.

1
2
3
4
5
6
7
8
n, m = map(int, input().split())
lst = [[]] # 소와 축사의 인덱스가 1부터 시작하므로 미리 0번 리스트를 넣어둡니다. n번째 리스트는 n번째 소가 희망하는 축사 번호를 담습니다.
for i in range(n):
    lst.append(list(map(int, input().split()))[1:])
    
barn = [0] * (m+1) # 그리고 축사를 나타내는 배열도 만들어줍니다. 축사 인덱스도 1부터 시작하니 편의상 배열 크기를 m+1로 설정했습니다.
# 축사에 소가 배정되면 그 소의 번호를 넣어줄 겁니다.

축사 배정 문제의 처음 그래프 상태는 다음과 같습니다.

매칭을 시작하기 전 앞서 설명한 이분 매칭 규칙을 코드로 표현해봅시다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# x번째 소 매칭 함수
def sol(x):
    if visited[x]: # 방문 배열. 이미 처리한 노드라면 False를 반환.
        return False
    
    visited[x] = 1
    
    for i in lst[x]: # x번째 소가 희망하는 축사를 하나씩 살펴봅니다.
        if not barn[i] or sol(barn[i]): # 희망하는 축사가 비어있거나(아직 매칭 안된 상태) 혹은 이미 해당 축사 안에 있는 소가 다른 데로 갈 수 있다면, 
            barn[i] = x # 축사 i에 x번째 소를 넣습니다.
            return True

    return False

이제 1번 소부터 축사에 넣어봅시다. 일단 1번 소는 2번 축사로 들어가고 싶어하네요. 2번 축사에 넣어줍시다.

그런데 2번 소도 2번 축사에 들어가고 싶어하네요. 이미 2번 축사에 1번 소가 있지만, 1번 소는 5번도 괜찮다고 하니까 1번 소를 5번 축사로 옮겨주고 2번 소는 2번 축사에 넣습니다. 3번 소는 그대로 1번 축사에 넣어주면 되겠네요. 3번 소까지 처리하면 그래프 상황이 아래와 같습니다.

복잡해지는 건 4번 소부터입니다.

  1. 우선 4번 소가 희망하는 첫 번째 축사가 1번인데, 이미 3번 소가 들어가 있으므로 3번 소가 희망하는 다른 축사(5번)가 있는지 본다.
  2. 5번 축사도 이미 1번 소가 들어가 있다. 따라서 이제는 1번 소가 희망하는 다른 축사(2번)가 있는지 살펴본다.
  3. 2번 축사를 보니까 이미 2번 소가 들어가 있다. 이에 2번 소가 희망하는 다른 축사(3번, 4번)를 살펴본다.
  4. 마침 3번 축사가 비어 있으니 2번 소를 3번 축사에 넣어준다.
  5. 그리고 1번 소는 2번 소가 비워준 2번 축사에 넣는다.
  6. 3번 소는 1번 소가 비워준 5번 축사에 넣는다.
  7. 4번 소는 이제 1번 축사로 갈 수 있다.

이러면 아래와 같이 축사 배정이 됩니다.

하지만 5번 소는 매칭이 안됩니다. 따라서 위의 결과가 최종적으로 축사 배정이 완료된 그림입니다. 5번 소는 마음에 안 들어도 4번 축사에 갈 수밖에 없겠네요. 아무튼 희망하는 축사에 최대한 매칭시키면 최대 네 마리까지 희망하는 축사에 들어갈 수 있습니다.


전체 코드

궁금하신 분을 위해 전체 코드를 준비했습니다.

전체 코드 접기/펼치기 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

n, m = map(int, input().split())
lst = [[]]
for i in range(n):
    lst.append(list(map(int, input().split()))[1:])
    
barn = [0] * (m+1)

def sol(x):
    if visited[x]:
        return False
    
    visited[x] = 1
    
    for i in lst[x]:
        if not barn[i] or sol(barn[i]):
            barn[i] = x
            #print(barn, x)
            return True

    return False


count = 0

for i in range(1, n+1):
    visited = [0] * (n+1)
    if sol(i):
        count += 1
    
    
print(count)

위와 같이 dfs 구조로 코드를 작성하시면 시간복잡도가 O(V * E)가 됩니다.
이해가 잘 되셨는지 궁금하네요. 글을 읽고 직접 문제를 풀어보셨으면 좋겠습니다.