이분 매칭

이분 매칭은 서로 다른 집단인 A집단과 B집단을 서로 매칭 시켜주는 주는 것 이다.

두 개의 정점 그룹이 존재할 때 모든 간선(경로)의 용량이 1이면서 양쪽 정점이 서로 다른 그룹에 속하는 그래프를 이분 그래프라고 하고 표현해 줄 수 있다.

예를 들어 다음 사진과 같이 두 집 단이 있다.
다음 그래프를 가장 효율적으로 매칭하는 경우는 두 집단이 최대로 매칭되는 경우다.

이분 탐색은 DFS(깊이 탐색)을 활용하여서 문제를 해결할 수 있다.

1. 정점 0의 경우 정점 3에 아무 것도 연결되어 있지 않으므로 정점 3과 연결
2. 정점 1의 경우 정점 3,4와 연결이 가능한데 이미 3이 연결 되어 있으므로 4번으로 연결
3. 정점 2의 경우 4번밖에 연결을 할 수 없는데 이미 4번은 1번과 연결되어 있음
   3-1. 정점 1을 확인해서 다른 것과 연결이 가능한지 확인.
   3-2. 정점1은 정점 3과 연결이 가능
   3-3. 정점 0을 확인해서 다른 것과 연결이 가능한지 확인.
   3-4. 정점 0은 정점 5와 연결이 가능
   3-5. 가능한 것들끼리 배치해주면서 정점 0

def bimatch(N):                                           
    if visited[N]:                                        
        return False                                      
    visited[N] = True                                     
                                                          
    for g in graph[N]:             
        # 매칭이 안 된 정점이거나, 이미 매칭된 정점이 다른 정점으로 바꿀 수 있는 경우           
        if selected[g] == -1 or bimatch(selected[g]):         
            selected[g] = N                                
            return True                                   
                                                          
    return False          


# A그룹 정점수, B그룹 정점수
n, m = map(int, input().split())

# A 정점에서 연결 가능한 B 정점 번호들
graph = [list(map(int, input().split())) for _ in range(n)]

# B 그룹과 매칭된 A 그룹 정점 번호 
selected = [-1] * (m + 1)

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


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

print(selected) # 연결 되었는지 확인
print(ans) # 최대 연결 갯수 출력