import sys
input = sys.stdin.readline
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
def Graph():
num = [[[0]*M for i in range(N)] for i in range(2)]; r = c = 0
for i in range(N):
for j in range(M):
if board[i][j]!=2:
if board[i][j-1]==2:
r += 1
num[0][i][j] = r
for j in range(M):
for i in range(N):
if board[i][j]!=2:
if board[i-1][j]==2:
c += 1
num[1][i][j] = c
graph = [[] for i in range(r+1)]
for i in range(N):
for j in range(M):
if not board[i][j]:
graph[num[0][i][j]].append(num[1][i][j])
return r,c,graph
N,M = map(int,input().split())
board = [[*map(int,input().split()),2] for i in range(N)]+[[2]*M]
r,c,graph = Graph()
match = [0]*(c+1)
for i in range(r+1):
visited = [0]*(r+1)
DFS(i)
print(c+1-match.count(0))
이분매칭 응용문제
몇달 전, 백트래킹 문제인 N-Queen 문제와 비숍 [백준 1799번] 비숍 (Python3) (tistory.com) 문제를 해결하고서, 자신감을 얻은 내가 호기롭게 도전했다가 깨졌던 문제이다. 여러 방법을 시도하다가 결국 실패하고 태그를 확인했는데, 백트래킹이 아닌 이분매칭을 이용해야한다는 것을 알고 접어두었다가 드디어 해결할 수 있게 되었다.
돌멩이 제거 [백준 1867번] 돌멩이 제거 (Python3) (tistory.com) 문제와 유사하다. 다만 "벽"의 존재 때문에 약간 더 추가해주어야할 요소가 있다.
풀이를 설명하면,
1. 각 행과 열을 벽을 기준으로 나누어 번호를 부여한다. 예를들어 첫번째 행이 벽으로 나누어진다면, 첫번째 행의 번호는 1번이 아니라 1번과 2번이 되고, 두번째 행은 3번부터 시작하게 된다.
2. 각 행과 열에 대해서 아무것도 없는 지점을 간선으로 한다.
3. 행-열을 노드로 하는 이분그래프에 대해서 이분매칭으로 최대매칭수를 찾고 출력한다.
여담) 내 풀이가 파이썬 기준 성능 1위가 되었다.