def DFS(i):
if visited[i]:
return 0
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
return 0
N = int(input())
board = [[0]*N for i in range(N)]
for y,x in [map(int,input().split()) for i in range(int(input()))]:
board[y-1][x-1] = -1
R = 0
for k in range(N*2):
R += 1
for y in range(N):
if N>y>=0 and N>k-y>=0:
if board[y][k-y]<0:
R += 1
continue
board[y][k-y] = R
graph = [[] for i in range(R+1)]
C = 0
for k in range(-N+1,N):
C += 1
for y in range(N):
if N>y>=0 and N>y-k>=0:
if board[y][y-k]<0:
C += 1
continue
graph[board[y][y-k]].append(C)
M = 0; match = [0]*(C+1)
for r in range(1,R+1):
visited = [0]*(R+1)
M += DFS(r)
print(M)
이분매칭 응용문제
제목은 비숍이지만 풀이방식은 비숍 [백준 1799번] 비숍 (Python3) (tistory.com) 보다는 N-Rook [백준 1760번] N-Rook (Python3) (tistory.com) 과 비슷하다. N-Rook에서 행과 열에 번호를 매기고 벽이 존재하면 번호를 나누었듯이 대각선을 행과 열로 취급하여 풀어주면 된다.
여담) 내 풀이가 파이썬 기준 성능 1위가 되었다.