[백준] 2188번 축사 배정 (Python)

백준 2188 가르침

시간초과에 늪에서 벗어나지 못해서 구글링을 해보니 이분 매칭 알고리즘을 활용해서 풀어야 한다. DFS를 활용하여 이분 매칭 알고리즘을 구현했다.

이분 매칭 알고리즘에 대하여

import sys

def DFS(cowNum):
    if cowNum == -1 or put[cowNum]:
        return 0
    put[cowNum] = True
    for want in cow[cowNum]:
        if barn[want] == -1 or DFS(barn[want]):
            barn[want] = cowNum
            return 1
    return 0

inp = sys.stdin.readline
n, m = map(int, inp().split())
cow = [[] + list(map(int, inp().split()[1:])) for _ in range(n)]
barn = [-1 for _ in range(m + 1)]

for i in range(n):
    put = [False for _ in range(n)]
    DFS(i)

print(m + 1 - barn.count(-1))