백준 온라인 저지, 이분매칭 / 2188번: 축사배정 (파이썬 / 백준 플레티넘문제)

문제 주소: https://www.acmicpc.net/problem/2188

문제

농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다.

첫 주에는 소를 임의 배정해서 축사를 운영했으나, 곧 문제가 발생하게 되었다. 바로 소가 자신이 희망하는 몇 개의 축사 외에는 들어가기를 거부하는 것이다.

농부 존을 도와 최대한 많은 수의 소가 축사에 들어갈 수 있도록 하는 프로그램을 작성하시오. 축사의 번호는 1부터 M까지 매겨져 있다.

입력

첫째 줄에 소의 수 N과 축사의 수 M이 주어진다. (1 ≤ N, M ≤ 200)

둘째 줄부터 N개의 줄에는 각 소가 들어가기 원하는 축사에 대한 정보가 주어진다. i번째 소가 들어가기 원하는 축사의 수 S_i (0 ≤ S_i ≤ M)이 먼저 주어지고, 이후 S_i개의 축사 번호가 주어진다. 같은 축사 번호가 두 번 이상 주어지는 경우는 없다.

출력

첫째 줄에 축사에 들어갈 수 있는 소의 최댓값을 출력한다.

제한

예제 입력 1

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

예제 출력 1

4

힌트

접근 방법

- 전형적인 이분매칭 문제이다.
- 소의 번호를 인덱스로하고 가고싶은 축사의 번호를 값으로 갖는 리스트(cow)를 만들고 축사의 번호를 인덱스로하고 그 축사에 배정받은 소의 번호를 값으로 갖는 리스트(cattle_shed)를 만든다.
- 이후 dfs를 통해 이분매칭을 구현한다.

코드

# 접근 방법
# 전형적인 이분매칭 문제이다.
# 소의 번호를 인덱스로하고 가고싶은 축사의 번호를 값으로 갖는 리스트(cow)를 만들고 축사의 번호를 인덱스로하고 그 축사에 배정받은 소의 번호를 값으로 갖는 리스트(cattle_shed)를 만든다.
# 이후 dfs를 통해 이분매칭을 구현한다.

import sys

def dfs(cow_number):
    if visited[cow_number]:
        return False
    visited[cow_number] = True
    
    for i in cow[cow_number]:
        if not cattle_shed[i] or dfs(cattle_shed[i]):
            cattle_shed[i] = cow_number
            return True
            
    return False
            
input = sys.stdin.readline
n, m = map(int, input().split())
cow = [[] for _ in range(n+1)]
cattle_shed = [0 for _ in range(m+1)]
for i in range(1, n+1):
    array = list(map(int, input().split()))
    for j in array[1:]:
        cow[i].append(j)
        
for i in range(1, n+1):
    visited = [False for _ in range(n+1)]
    dfs(i)
    
print(sum([1 for i in cattle_shed if i > 0]))