[백준 11014번] 컨닝 2 (Python3)

def DFS(y,x):
  if visited[y][x]:
    return 0
  visited[y][x] = 1
  for y1,x1 in graph[y][x]:
    if not match[y1][x1]:
      match[y1][x1] = y,x
      return 1
  for y1,x1 in graph[y][x]:
    if DFS(*match[y1][x1]):
      match[y1][x1] = y,x
      return 1
  return 0

for _ in range(int(input())):
  N,M = map(int,input().split())
  board = [[*map(lambda x:int(x=="."),input())] for i in range(N)]
  graph = [[[] for x in range(M)] for y in range(N)]
  for x in range(M//2):
    x = x*2+1
    for y in range(N):
      if board[y][x]:
        for i in [-1,0,1]:
          for j in [-1,1]:
            if N>y+i>=0 and M>x+j>=0 and board[y+i][x+j]:
              graph[y][x].append((y+i,x+j))
  match = [[0]*M for i in range(N)]
  m = 0
  for x in range(M//2):
    x = x*2+1
    for y in range(N):
      if board[y][x]:
        visited = [[0]*M for i in range(N)]
        m += DFS(y,x)
  print(sum(map(sum,board))-m)

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

컨닝1 [백준 1014번] 컨닝 (Python3) (tistory.com) 문제에서 N,M의 범위가 10에서 80으로 늘어났다. 따라서 컨닝1 문제에서처럼 비트마스킹 풀이는 사용할 수 없다.

 

풀이를 설명하면,

1. 교실의 각 책상을 정점으로 두고, 각 정점에서 컨닝할 수 있는 정점으로의 간선이 있다고 하면, 홀수열 정점-짝수열 정점으로 이루어지는 이분그래프로 볼 수 있다.

2. 각 홀수열 정점에서 컨닝할 수 있는 정점으로의 간선을 인접그래프로 표현한다.

3. 이분매칭으로 최대매칭수를 구하고, 전체 정점의 수 - 최대매칭수를 출력한다.

 

3이 성립하는 이유는 콰닉의 정리에 따라 최소커버정점 = 최대매칭수와 같고, 최대독립집합은 전체정점에서 최소커버정점을 뺀 값과 같기 때문이다.

 

이분매칭 문제임을 알고 있음에도 이분그래프임을 파악하기 쉽지 않았고, 이분매칭으로 최대매칭수를 구했을 때 왜 답이 나오는지에 대한 이론도 찾아봐야하는 어려운 문제였다.

 

 

오늘의 교훈) 이분그래프에서 최대독립집합 = 전체정점 - 최소커버정점 수(최대 매칭수)