백준 온라인 저지, 이분매칭 / 11377번: 열혈강호3 (파이썬 / , 백준 플레티넘문제)

문제

강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다.

각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 단, N명 중에서 K명은 일을 최대 2개할 수 있다.

각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N)

둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다.

출력

첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다.

제한

예제 입력 1

5 5 1
3 1 2 3
3 1 2 3
1 5
1 5
1 5

예제 출력 1

4

힌트

1번 사람이 일을 2개하면, 1번 사람은 1, 2, 2번 사람은 3, 3번 사람이 5를 할 수 있다.

접근 방법

- 처음 모든 사람에 대해 이분 매칭을 진행한 뒤, 다시 한번 모든 인원에 대해 이분 매칭을 진행한다. 이때 이분매칭으로 일이 매칭된 사람들은 최대 k명까지만 되야하므로 k명이 넘게되면 이를 중단하고 값을 출력한다.

코드

# https://www.acmicpc.net/problem/11377
# 접근 방법
# 처음 모든 사람에 대해 이분 매칭을 진행한 뒤, 다시 한번 모든 인원에 대해 이분 매칭을 진행한다. 이때 이분매칭으로 일이 매칭된 사람들은 최대 k명까지만 되야하므로 k명이 넘게되면 이를 중단하고 값을 출력한다.
def dfs(i):
    if visited[i]:
        return False
    visited[i] = True
    for x in emp[i]:
        if not work[x] or dfs(work[x]):
            work[x] = i
            return True
    return False


import sys
n, m, k = map(int, input().split())
emp = [[] for _ in range(n+1)]
work = [0 for _ in range(m+1)]
for i in range(1, n+1):
    temp = list(map(int, input().split()))
    emp[i] = temp[1:]

count = 0
for i in range(1, n+1):
    visited = [False for _ in range(n+1)]
    if dfs(i):
        count += 1

for i in range(1, n+1):
    visited = [False for _ in range(n+1)]
    if dfs(i):
        count += 1
        k -= 1
        if k == 0:
            break
print(count)