전체 코드

def binary_matching():
    def bimatch(N):
        if visited[N]:
            return False
        visited[N] = True

        for num in graph[N]:
            if selected[num] == -1 or bimatch(selected[num]):
                selected[num] = N
                return True

        return False

    # 왼쪽 정점수, 오른쪽 정점 수
    n, m = 5, 5

    # 왼쪽 정점에서 연결 가능한 오른쪽 정점 번호들
    graph = [[2, 5], [2, 3, 4], [1, 5], [1, 2, 5], [2]]

    # 선택된 정점 번호
    selected = [-1] * (m + 1)

    for i in range(n):
        visited = [False] * (n)
        bimatch(i)
    
    
    # 결과 출력
    result = 0
    for i in range(1, m+1):
        if selected[i] >= 0:
            result += 1
    
    return result

print(binary_matching())

코드

# 왼쪽 정점수, 오른쪽 정점 수
n, m = 5, 5

# 왼쪽 정점에서 연결 가능한 오른쪽 정점 번호들
graph = [[2, 5], [2, 3, 4], [1, 5], [1, 2, 5], [2]]

# 선택된 정점 번호
selected = [-1] * (m + 1)

대충 위의 그래프를 이렇게 만들어 두고,

for i in range(n):
    visited = [False] * (n)
    bimatch(i)

각 정점들을 순회하며 bimatch함수를 호출해주자.

visited 배열은 이미 확인한 왼쪽 정점들을 다시 확인하지 않기 위함이다.

def bimatch(N):
    if visited[N]:
        return False
    visited[N] = True

    for num in graph[N]:
        if selected[num] == -1 or bimatch(selected[num]):
            selected[num] = N
            return True

    return False

if문 내에서 bimatch함수를 재호출하면서 DFS로 가능한 정점을 탐색한다.

result = 0
for i in range(1, m+1):
    if selected[i] >= 0:
        result += 1

마지막으로 선택된 정점들의 개수를 세면 끝!

이분 매칭은 A, B로 나뉜 이분 그래프에서 A에서 B로 이동하는 최대 유량... 어쩌구... 는 모르겠고, 그래프에서 정점들의 집합을 두개로 나눴을 때, 한 집합의 정점에서 다른 정점의 집합으로 1:1(혹은 1: M)으로 중복되지 않게 연결할 수 있는 최대 간선 개수 정도라고하면 되려나..

아무튼 대충 그림으로 설명하면

이런 이분 그래프가 있을 때,

이렇게 겹치지 않게 정점들을 매칭할 때, 만들 수 있는 최대 간선 수라고 보면 될 거 같다.