https://www.acmicpc.net/problem/11375
시간 2초, 메모리 256MB

input :

• N M (1 ≤ N, M ≤ 1,000)
• i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호

output :

• 강호네 회사에서 할 수 있는 최대의 일의 개수를 출력

조건 :

• 직원은 1번부터 N번까지, 일은 1번부터 M번까지 번호가 매겨져 있다.

• 각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다.

---

이분매칭의 대표적인 문제인데 시간 제한 때문에 좀 애를 먹었다. 그리고 그 시간제한이 열혈강호 3에서도 문제가 생겼다...

우선적으로 할 수 있는 일이 존재하는지 확인, dfs를 수행하는 것은 그 다음으로 해야 한다.
결국에는 dfs가 시간을 많이 허비하기 떄문에 그렇다.
그 이전에 다른 조건들을 확인해야 한다.

다음 풀이

1. 각각의 일은 1명이 담당
2. 시간 제한

이분 매칭이란 것은 쉽게 확인할 수 있다.
최대한 많은 일을 하는데 정해진 인원이 있기 때문에 이를 통해 알 수 있다.
그래서 main()함수를 통해 사용해서 시간을 더 줄이고, 내부에서도 cnt == m 조건 dfs()에서는 ans에 비어있는 답이 있는지 부터 확인 하도록 한다.

이렇게 시간을 줄이게 되면 최적의 답을 얻을 수 있다.
추가적인 함수를 수행하는 부분들을 나중(조건을 수행한 후)에 하도록 하여 시간적 이득을 얻어야 한다.

import sys

def main():
    def dfs(visit, node):
        if visit[node] == 1:
            return 0
    
        visit[node] = 1
    
        for key in employee[node]:
            if ans[key] == 0:
                ans[key] = node
                return 1
    
        for key in employee[node]:
            if dfs(visit, ans[key]):
                ans[key] = node
                return 1
    
        return 0
    
    n, m = map(int, sys.stdin.readline().split())
    employee, ans = [[] for _ in range(n + 1)], [0] * (m + 1)
    
    for i in range(1, n + 1):
        temp = list(map(int, sys.stdin.readline().split()))
        for item in temp[1:]:
            employee[i].append(item)
    
    cnt = 0
    for i in range(1, n + 1):
        visit = [0] * (n + 1)
        if dfs(visit, i):
            cnt += 1
    
        if cnt == m:
            break
    
    print(cnt)

if __name__=="__main__":
    main()