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

문제

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

각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 여기서 지난달에 벌점을 X점 받은 사람은 일을 최대 X+1개까지 할 수 있다.

예를 들어, 직원이 3명이고, 지난달에 1번 직원 민호가 벌점을 2점, 2번 직원 재필이가 벌점을 1점, 3번 직원 주현이가 벌점을 0점 받았다면, 1번 직원 민호는 일을 최대 3개, 2번 직원 재필이는 최대 2개, 3번 직원 주현이는 최대 1개까지 할 수 있다.

각 직원은 자신이 지난달에 받은 벌점을 알지 못하고, 직원이 받은 벌점의 합 K만을 알고 있다. 강호는 이런 사실을 이용해서 벌점을 적절히 나눠서 최대한 일을 많이 할 수 있게 하려고 한다.

예를 들어, 1번 직원이 1, 2, 3, 4, 5를 할 수 있고, 2, 3, 4번 직원이 1을 할 수 있고, 5번 직원이 1, 5를 할 수 있는 경우를 생각해보자.

지난 달에 전직원이 받은 벌점의 합 K가 0이라면, 할 수 있는 일의 최대 개수는 3개이다. 1번 직원이 2를 하고, 2번 직원이 1을, 5번 직원이 5를 하면 된다. 

벌점의 합 K가 2인 경우에, 1번 직원이 1점, 5번 직원이 1점을 받았다고 하면, 일을 최대 4개 할 수 있다. 1번 직원과 5번직원은 이제 일을 2개까지 할 수 있다. 1번 직원이 2와 3을, 5번 직원이 1과 5를 하면 총 4개의 일을 할 수 있다. 하지만, 강호가 벌점을 조작해 1번 직원이 2점을 받았다고 하면, 일은 최대 5개 할 수 있게 된다. 1번 직원은 일을 3개까지 할 수 있다. 따라서, 1번 직원이 2, 3, 4를 하고, 2번 직원이 1을, 5번 직원이 5를 하면 5개를 모두 할 수 있게 된다.

벌점의 합 K가 3인 경우에는, 1번 직원에게 벌점을 모두 몰아주면 일을 5개 할 수 있다. 1번 직원은 벌점이 3점이기 때문에, 일을 총 4개까지 할 수 있다. 따라서, 1, 2, 3, 4를 모두 1번직원이 하고, 5번 직원이 5를 하면 총 5가지 일을 할 수 있게 된다.

각각의 직원이 할 수 있는 일의 목록과 지난달 받은 벌점의 합 K가 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 직원의 수 N과 일의 개수 M, 지난달에 받은 벌점의 합 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N)

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

출력

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

제한

예제 입력 1

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

예제 출력 1

4

예제 입력 2

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

예제 출력 2

5

예제 입력 3

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

예제 출력 3

5

예제 입력 4

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

예제 출력 4

5

힌트

접근 방법

- 처음 모든 사람에 대해 이분매칭을 동작한 뒤, 한번 더 모든 사람에 대해 이분 매칭을 반복한다. 단, 한 사람에 대해서 while 반복문을 활용해 dfs가 true일 경우 이를 반복해주며, k를 줄여나가고 만약 k가 0이라면 이분 매칭을 멈추고 결과를 출력한다.

코드

# https://www.acmicpc.net/problem/11378
# 접근 방법
# 처음 모든 사람에 대해 이분매칭을 동작한 뒤, 한번 더 모든 사람에 대해 이분 매칭을 반복한다. 단, 한 사람에 대해서 while 반복문을 활용해 dfs가 true일 경우 이를 반복해주며, k를 줄여나가고 만약 k가 0이라면 이분 매칭을 멈추고 결과를 출력한다.
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
input = sys.stdin.readline
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):
    while True:
        visited = [False for _ in range(n+1)]
        if not dfs(i) or k == 0:
            break
        count += 1
        k -= 1
        
    if k == 0:
        break
print(count)