[백준 3683번] 고양이와 개 (Python3)

import sys
input = sys.stdin.readline

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

for _ in range(int(input())):  
  C,D,N = map(int,input().split())
  yes,no = [[[] for i in range(C+D+1)] for i in range(2)]
  for i in range(N):
    y,n = input().split()
    yes[int(y[0]=="D")*C+int(y[1:])].append(i)
    no[int(n[0]=="D")*C+int(n[1:])].append(i)
  graph = [[] for i in range(N)]
  for i in range(C+D+1):
    for y in yes[i]:
      for n in no[i]:
        if i>C:
          graph[n].append(y)
        else:
          graph[y].append(n)
  match = [-1]*N
  for i in range(N):
    visited = [0]*N
    DFS(i)
  print(match.count(-1))

이분매칭 + 콰닉의 정리 응용문제

이분매칭 문제임을 알고 문제를 풀었는데도 왜 이분매칭인지 파악하기 쉽지 않은 문제였다. 시청자를 고양이를 좋아하는 집단과 개를 좋아하는 집단, 두 집단으로 분리하는것이 핵심이다.

 

풀이를 설명하면,

1. 고양이파 - 개파의 이분그래프를 그린다. 고양이파 i와 개파 j가 있을 때, i가 올리고 싶은 고양이와 j가 떨어뜨리고 싶어하는 고양이가 같을 경우, 혹은 개가 같을 경우 간선을 그린다.

2. 이분매칭을 실행하고, 전체 인원에서 최대매칭수를 뺀 것이 곧 최대독립집합으로 시청자 수의 최댓값이다. (콰닉의 정리)

 

 

오늘의 교훈) 주어진 문제에서 두개로 분리하여 볼 수 있는지를 세심하게 관찰하자