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

문제

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

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

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

입력

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

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

출력

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

제한

 

예제 입력 1

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

예제 출력 1

4 

힌트

 

접근 방법

- 전형적인 이분 매칭 문제이다.
- 직원의 번호를 인덱스로 하고, 할 수 있는 일의 번호를 값으로 가지는 리스트(employee)와 일의 번호를 인덱스로 하고, 그 일을 하는 직원의 번호를 값으로 가지는 리스트(work)를 초기화한다.
- 이후 dfs를 통해 이분매칭을 구현한다.

코드

# 접근 방법
# 전형적인 이분 매칭 문제이다.
# 직원의 번호를 인덱스로 하고, 할 수 있는 일의 번호를 값으로 가지는 리스트(employee)와 일의 번호를 인덱스로 하고, 그 일을 하는 직원의 번호를 값으로 가지는 리스트(work)를 초기화한다.
# 이후 dfs를 통해 이분매칭을 구현한다.

def dfs(employee_number):
    if visited[employee_number]:
        return False
        
    visited[employee_number] = True
    for work_number in employee[employee_number]:
        if not work[work_number] or dfs(work[work_number]):
            work[work_number] = employee_number
            return True
    
    return False

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
employee = [[]]
for _ in range(n):
    temp = list(map(int, input().split()))
    employee.append(temp[1:])
work = [0 for _ in range(m+1)]
for i in range(1, n+1):
    visited = [False for _ in range(n+1)]
    dfs(i)
print(sum([1 for x in work if x > 0]))