[BOJ] - python 열혈강호 (최대유량 + 이분매칭)

https://www.acmicpc.net/problem/11375

11375번: 열혈강호

그냥 갑자기 에드몬드 카프 알고리즘이 떠올라서,,,? class7 도장깨기 하고 있는데, 이분매칭 간단한 문제가 있길래 풀어봤다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
ans = 0

def dfs(n):
    for i in task[n]:
        if check[i]: continue
        check[i] = 1
        if not visited[i] or dfs(visited[i]):
            visited[i] = n
            # 매칭이 된 것이므로 True를 리턴해준다.
            return 1
    # 이분매칭에서 매칭이 안되는 경우는 False를 리턴해준다.    
    return 0
    
N, M = map(int, input().split())
task = [[]] + [list(map(int, input().split()))[1:] for _ in range(N)]
# print(task)
visited = [0] * (M + 1)

for i in range(1, N + 1):
    check = [0] * (M + 1)
    if dfs(i):
        ans+=1
print(ans)

이분매칭은 간단히 말하면 A 집단이 B집단을 선택하게 하는 방법에 관련된 알고리즘입니다. 즉 어떤 집단들 간에 가장 효과적으로 매칭시켜 줄 수 있는 경우가 어떠한 경우인지 알아내는데, 이를 그래프 형태로 풀어내는 것이라고 할 수 있겠습니다.

 

효과적이라는 것은 '최대 매칭(Max Matching)'을 의미합니다. 모든 사람 각각이 노트북을 선택하여 가장 많이 연결되는 경우를 찾는 문제라고 볼 수 있습니다. 네트워크 플로우로 표현하게 되었을 때. 각 용량(Capacity)를 1로 설정한 네트워크 플로우 문제로 이해할 수 있게 되는데, 애드몬드 카프 알고리즘은 $O(V * E^{2})$의 시간복잡도를 가집니다. 하지만 이를 적용하게 되면 TLE가 납니다.

 

따라서 $O(V * E)$로 DFS로 해결가능한 이분매칭으로 이를 해결하면 됩니다.