[BOJ 2188] 축사 배정

문제

---

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

풀이

---

이분 매칭 문제인데 최대 유량 개념으로도 풀 수 있다.

sink, source 노드를 새로 만들고, sink에선 각 소들로, 각 축사들에선 source로 엣지를 이어준다.

각 소 별로 원하는 축사에도 엣지를 이어준다.

그렇게 구성된 flow network에서 최대 유량이 정답이 된다.

코드

---

import sys


def dfs(cur):
    visit[cur] = 1
    if cur == n + m + 1:
        return 1
    
    for nxt in range(1, n + m + 2):
        if graph[cur][nxt] and not visit[nxt]:
            if dfs(nxt):
                graph[cur][nxt] = 0
                graph[nxt][cur] = 1
                return 1
    
    return 0


n, m = map(int, sys.stdin.readline().split())
graph = [[0] * (n + m + 2) for _ in range(n + m + 2)]

for i in range(1, n + 1):
    data = list(map(int, sys.stdin.readline().split()))
    for j in range(data[0]):
        graph[i][n + data[1 + j]] = 1

for i in range(n + 1):
    graph[0][i] = 1

for i in range(n + 1, n + m + 1):
    graph[i][n + m + 1] = 1

ans = 0
flow = 1
while flow:
    visit = [0] * (n + m + 2)
    flow = dfs(0)
    ans += flow

print(ans)