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]*N for i in range(N)] for i in range(2)]; r=c=0
for i in range(N):
for j in range(N):
if board[i][j]!=2:
if board[i][j-1]==2:
r += 1
num[0][i][j] = r
for j in range(N):
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(N):
if not board[i][j]:
graph[num[0][i][j]].append(num[1][i][j])
return r,c,graph
N = int(input())
board = [[*map(lambda x:0 if x=="." else 2,input()),2] for i in range(N)]+[[2]*N]
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))
= [백준 1760번] N-Rook (Python3) (tistory.com)
웅덩이는 없고 벽만 있는 N-Rook 문제이다. 풀이가 사실상 똑같다.
여담) 이 문제도 파이썬 기준 성능 1위를 하였다.