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

문제

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

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

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

입력

첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000)

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

출력

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

제한

예제 입력 1

5 5
2 1 2
2 1 2
2 1 2
2 4 5
0

예제 출력 1

4

힌트

접근 방법

- 전형적인 이분매칭 문제이다.
- 직원번호를 인덱스로, 그 직원이 해야할 일을 값으로 가지는 직원 그래프, 일의 번호를 인덱스로, 그 일에 매칭이 된 직원의 번호를 값으로 가지는 리스트를 만든다.
- 이후 dfs를 통해 직원을 각 일에 매칭시켜준다.
- 단 각 사람 당 최대 두 개의 일을 맡을 수 있으므로 일의 개수를 저장할 리스트를 따로 만들어 일을 맡은 개수를 관리한다.
- 이미 한번 일을 맡은 직원의 경우 dfs를 통해 이분 매칭을 구현할 경우 맡은 일이 없어지지는 않기에 이를 고려하여 dfs를 구현한다.

코드

# 접근 방법
# 전형적인 이분매칭 문제이다.
# 직원번호를 인덱스로, 그 직원이 해야할 일을 값으로 가지는 직원 그래프, 일의 번호를 인덱스로, 그 일에 매칭이 된 직원의 번호를 값으로 가지는 리스트를 만든다.
# 이후 dfs를 통해 직원을 각 일에 매칭시켜준다.
# 단 각 사람 당 최대 두 개의 일을 맡을 수 있으므로 일의 개수를 저장할 리스트를 따로 만들어 일을 맡은 개수를 관리한다.
# 이미 한번 일을 맡은 직원의 경우 dfs를 통해 이분 매칭을 구현할 경우 맡은 일이 없어지지는 않기에 이를 고려하여 dfs를 구현한다.

def dfs(number):
    if visited[number]:
        return False
    visited[number] = True
    for t in employee[number]:
        if number != task[t] and (not task[t] or dfs(task[t])):
            task[t] = number
            return True
    return False

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
employee = [[] for _ in range(n+1)]
task = [0 for _ in range(m+1)]
count = [0 for _ in range(n+1)]
for i in range(1, n+1):
    temp = list(map(int, input().split()))
    employee[i] = temp[1:]

for number in range(1, n+1):
    visited = [False for _ in range(n+1)]
    dfs(number)
    visited = [False for _ in range(n+1)]
    dfs(number)

print(sum(1 for x in task if x > 0))
# print(task)