[백준 9525번] 룩 배치하기 (Python3)

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위를 하였다.