본문 바로가기

카테고리 없음

[백준 2188번] 축사 배정 (Python)

def DFS(i):
  if visited[i]:
    return
  visited[i] = 1
  for j in graph[i]:
    if match[j]<0:
      match[j] = i
      return 1
  for j in graph[i]:
    if DFS(match[j]):
      match[j] = i
      return 1

N,M = map(int,input().split())
graph = [[*map(int,input().split())][1:] for i in range(N)]
match = [-1]*(M+1)
for i in range(N):
  visited = [0]*N
  DFS(i)
print(M+1-match.count(-1))

= [백준 11375번] 열혈강호 (Python3) (tistory.com)

이분매칭 기본문제이다.