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이 성립하는 이유는 콰닉의 정리에 따라 최소커버정점 = 최대매칭수와 같고, 최대독립집합은 전체정점에서 최소커버정점을 뺀 값과 같기 때문이다.
이분매칭 문제임을 알고 있음에도 이분그래프임을 파악하기 쉽지 않았고, 이분매칭으로 최대매칭수를 구했을 때 왜 답이 나오는지에 대한 이론도 찾아봐야하는 어려운 문제였다.
오늘의 교훈) 이분그래프에서 최대독립집합 = 전체정점 - 최소커버정점 수(최대 매칭수)