[463] 이분 매칭 알고리즘 과정 살펴보기(파이썬 코드)

1. 입력 정보

왼쪽 정점(a그룹)의 개수 N, 오른쪽 정점(b그룹)의 개수 M

다음 N개의 줄에 왼쪽 정점에 연결된 간선의 개수와 오른쪽 정점의 정보

5 5
2 1 3
3 1 2 4
2 1 2
2 1 2
1 3

N, M = map(int, input().split())

 

2. 필요한 자료구조 살펴보기

가. 각 왼쪽 정점에 연결되어 있는 오른쪽 정점들: b_list

나. 왼쪽 정점의 방문 기록: visited

다. 오른쪽 정점에 짝지어진 왼쪽 정점: b_match

b_list =[[] for _ in range(N+1)]
for i in range(1, N+1):
    b_list[i].extend([*map(int, input().split())][1:])
visited = [False] * (N+1)
b_match = [-1] * (M+1)

3. 과정 살펴보기

가. 각 왼쪽 정점에서 DFS를 실시하여 오른쪽에서 짝찾기

이분 매칭은 왼쪽 정점과 오른쪽 정점을 짝짓기 때문에 아무리 커도 두 그룹의 정점의 수 중 작은 값을 넘지 않습니다.

def dfs(a):
    if visited[a]: return False
    visited[a] = True
    return False

cnt = 0
for a in range(1, N+1):
    visited = [False] * (N+1)
    if dfs(a): cnt += 1
    if cnt == min(N, M): break
print(cnt)

1) 왼쪽 정점과 연결된 오른쪽 정점 중 아직 짝이 없는 정점이 있다면 짝짓기

2) 연결된 모든 (오른쪽) 정점이 (왼쪽) 짝을 가지고 있을 경우, (왼쪽) 짝으로 부터 DFS를 시작하여 새로운 짝을 찾기

3) 새로운 짝을 찾으면 기존 짝을 새로운 짝으로 바꿔주고, 기존 짝은 DFS를 시작했던 왼쪽 정점과 짝짓기

왼쪽 1번 정점에서 DFS를 시작합니다. 연결된 오른쪽 정점이 짝이 없으므로 짝짓고 바로 DFS가 종료됩니다.

왼쪽 2번 정점에서 DFS를 시작합니다. 연결된 오른쪽 1번 정점이 짝이 있으므로, 다음 2번 정점을 살펴봅니다. 2번 정점은 짝이 없으므로 짝짓고 DFS가 종료됩니다.

def dfs(a):
    if visited[a]: return False
    visited[a] = True

    for b in b_list[a]:
        if b_match[b] == -1:
            b_match[b] = a
            return True
            
    return False

왼쪽 3번 정점에서 DFS를 시작합니다. 연결된 모든 오른쪽 정점이 짝이 있습니다.

왼쪽 3번 정점과 연결된 1번 정점과 짝지어진 왼쪽 1번 정점에서 DFS를 재귀적으로 실행합니다.

왼쪽 1번은 짝이 없는 3번을 발견하여 짝짓기에 성공합니다.

왼쪽 3번 정점은 이 소식을 재귀 함수 반환 결과로 알게 되고, 오른쪽 1번 정점과 짝을 짓습니다.

def dfs(a):
    if visited[a]: return False
    visited[a] = True

    for b in b_list[a]:
        if b_match[b] == -1:
            b_match[b] = a
            return True

    for b in b_list[a]:
        if not visited[b_match[b]] and dfs(b_match[b]):
            b_match[b] = a
            return True

    return False

이렇게 구현은 모두 끝이 났고, 나머지 과정을 그림을 통해 살펴보면 다음과 같은 과정을 거칩니다.

4번 정점도 짝 없는 오른쪽 정점 탐색을 실패하고, 오른쪽 1번 정점을 통해 왼쪽 3번 정점에서 DFS를 다시 시작합니다.

3번 정점도 짝 없는 오른쪽 정정 탐색을 실패하고, 오른쪽 1번 정점을 통해 자기 자신에서 DFS을 하려고 시도하지만 방문처리가 되어 있어서 다음인 오른쪽 2번 정점을 통해 왼쪽 2번 정점에서 DFS를 다시 시작합니다.

2번 정점에서 짝 없는 오른쪽 4번 정점을 찾았기 때문에 짝을 짓고, 재귀 함수를 마칩니다.

왼쪽 3번 정점은 DFS에 성공해 오른쪽 2번 정점과 짝을 짓고, 재귀 함수를 마칩니다.

왼쪽 4번 정점은 DFS에 성공해 오른쪽 1번 정점과 짝을 짓고, DFS를 마칩니다.

이제 마지막 왼쪽 5번 정점에서 마지막 DFS를 시작합니다.

5번 정점은 짝 없는 오른쪽 정점을 찾지 못해 자신과 연결된 오른쪽 3번 정점의 짝인 왼쪽 1번 정점으로 가서 재귀적으로 DFS를 합니다.

역시 짝 없는 오른쪽 정점을 찾지 못해 오른쪽 1번 정점을 통해 왼쪽 4번 정점으로 가서 재귀적으로 DFS를 합니다.

역시 짝 없는 오른쪽 정점을 찾지 못했고, 왼쪽 4번 정점은 방문 처리가 되어 있으므로 오른쪽 2번 정점을 통해 왼쪽 3번 정점으로 가서 재귀적으로 DFS를 합니다.

결국 왼쪽 3번 정점도 오른쪽 짝 없는 정점을 찾지 못합니다. 그리고 오른쪽 정점을 통해 방문하지 않은 왼쪽 정점에도 탐색을 실패합니다. 이를 통해 재귀적으로 실행되었던 DFS가 모두 실패하고, 왼쪽 5번 정점은 짝을 찾지 못하고 종료됩니다.

이 과정을 통해 이분 매칭의 값은 4라는 것을 알 수 있습니다.

4. 완성된 이분 매칭 파이썬 코드

N, M = map(int, input().split())

b_list =[[] for _ in range(N+1)]
for i in range(1, N+1):
    b_list[i].extend([*map(int, input().split())][1:])
visited = [False] * (N+1)
b_match = [-1] * (M+1)

def dfs(a):
    if visited[a]: return False
    visited[a] = True

    for b in b_list[a]:
        if b_match[b] == -1:
            b_match[b] = a
            return True

    for b in b_list[a]:
        if not visited[b_match[b]] and dfs(b_match[b]):
            b_match[b] = a
            return True

    return False

cnt = 0
for a in range(1, N+1):
    visited = [False] * (N+1)
    if dfs(a): cnt += 1
    if cnt == min(N, M): break
print(cnt)