[백준 1760번] N-Rook (Python3)

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