[백준 1867번] 돌멩이 제거 (Python3)

import sys
def input(): return map(int,sys.stdin.readline().split())

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

N,M = input()
graph = [[] for i in range(N+1)]
for _ in range(M):
  a,b = input()
  graph[a].append(b)
match = [0]*(N+1)
for i in range(1,N+1):
  visited = [0]*(N+1)
  DFS(i)
print(N+1-match.count(0))

이분매칭 응용문제이자 콰닉의 정리 연습문제

콰닉의 정리에 대한 이론은 https://gazelle-and-cs.tistory.com/12 을 참고하였다.

 

풀이를 설명하면,

1. 그래프를 가로줄-세로줄을 노드로 하는 이분그래프라고 가정한다.

2. 돌멩이가 있는 위치가 곧 간선이다.

3. 이분매칭을 이용하여 최대매칭 개수를 찾으면, 콰닉의 정리에 따라 그 값이 곧 최소커버노드 개수이다.

 

콰닉의 정리를 공부할 수 있는 좋은 문제였다.

 

 

오늘의 교훈) 이분매칭과 콰닉의 정리를 활용해 다양한 문제를 해결하자