[파이썬] 백준 2188번: 축사 배정

https://www.acmicpc.net/problem/2188

2188번: 축사 배정

 

문제

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

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

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

입력

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

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

출력

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

예제 입력 1 복사

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

예제 출력 1 복사

4

 

- 이분 매칭 문제 ( DFS 활용)

# 이분매칭문제 (DFS 활용) : 한 집합에서 다른 집합으로 중복되지 않게 연결할 수 있는 최대 간선 개수
import sys
input=sys.stdin.readline

def dfs(num):
    if visited[num]: # 이미 확인한 소들을 확인하지 않기 위함
        return False
    visited[num]=True
    
    for i in graph[num]: # 가고싶은 축사 번호 리스트 중에서
        # 다른 소들에게 선택안된 곳이거나, 선택된 곳이면 해당 소가 다른 희망 축사로 갈 수 있으면
        if selected[i]==-1 or dfs(selected[i]):
            selected[i]=num # 현재 소를 배정
            return True # 배정됐으므로 True 리턴
  
    return False # 배정안됐으면 False 리턴

N,M=map(int,input().split())
graph=[[] for _ in range(N+1)] # 소마다 가고싶은 축사 번호 그래프
selected=[-1]*(M+1)
for i in range(1,N+1):
    arr=list(map(int,input().split()))
    for j in arr[1:]:
        graph[i].append(j) # 가고싶은 축사 번호 입력받기

for i in range(1,N+1):
    visited=[False]*(N+1)
    dfs(i) # 소마다 dfs돌려서 매칭 축사 찾기
    
result=0
# 마지막으로 selected 리스트에 -1이 아닌 즉 선택받은 번호들의 개수가 최댓값임
for i in range(1,M+1):
    if selected[i]>=0:
        result += 1
        
print(result)