[백준 2570번] 비숍2 (Python)

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위가 되었다.