[BOJ/python]11375번 열혈강호

백준 11375번 열혈강호 파이썬, 네트워크 플로우

출처 - https://www.acmicpc.net/problem/11375

11375번: 열혈강호

네트워크 플로우 연습하고 싶어서 푼 문제였지만 에드몬드 카프로 풀면 시간 초과가 나온다.

덕분에(?) 이분 매칭을 공부할 수 있었다. 네트워크 플로우에 대한 개념을 알고 있었기 때문에 약간의 힌트만 보고 풀 수 있었다.

1. 풀이

sink 노드와 source 노드 없이 직원과 일 노드만 그래프로 표현한다. match 배열을 통해 특정 일이 배정되었음을 표시한다.

• 모든 직원(node)에 대하여 DFS를 실행한다.
• 만약 일(next)이 배정되지 않았다면 직원을 일에 배정한다. 이 때 match[next]=node 로 표시한다.
• 만약 일(next)이 이미 배정되었다면, 해당 일에 배정된 직원(before)을 입력값으로 DFS를 실행한다. 이미 배정되었던 직원(before)이 새로운 일(두번째 재귀에서 next)에 배정된다면 새로운 직원(node)을 일(next)에 배정한다.
  • 만약 이미 배정되었던 직원(before)이 새로운 일에 배정되지 못한 경우(두번째 재귀에서 next)는 pass한다. (ex. before가 오직 next에만 배정 가능한 경우)
• for문에서 다음 일(next)로 넘어간다. 모든 next에 배정이 불가능하다면 false를 반환한다.

2. 코드

# 열혈강호 (이분매칭)
N,M = map(int, input().split())
path = [ [] for _ in range(N+1) ]
for i in range(N):
    line = list(map(int, input().split()))
    for j in (line[1:]):
        path[i+1].append(j)
        
match = [0 for _ in range(M+1)]    
def DFS(node):
    if visited[node] == 1:
        return False
    
    visited[node]=1
    
    for next in path[node]:
        if match[next] == 0 :
            match[next]=node
            return True
        
        else:
            before = match[next]
            if DFS(before) == True:
                match[next]=node
                return True
            
    return False
    

for i in range(1,N+1):
    visited=[0 for _ in range(N+1)]
    DFS(i)

sol=0
for i in range(M+1):
    if match[i]>0:
        sol+=1
print(sol)