[백준 1574번] 룩 어택 (Python3)

import sys
def input(): return map(int,sys.stdin.readline().split())

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

r,c,N = input()
board = [[1]*(c+1) for i in range(r+1)]
for _ in range(N):
  y,x = input()
  board[y][x] = 0
graph = [[] for i in range(r+1)]
for i in range(1,r+1):
  for j in range(1,c+1):
    if board[i][j]:
      graph[i].append(j)
match = [0]*(c+1)
for i in range(r+1):
  visited = [0]*(r+1)
  DFS(i)
print(c+1-match.count(0))

N-Rook [백준 1760번] N-Rook (Python3) (tistory.com) 하위호환 문제.

N-Rook에서 웅덩이만 있고 벽은 없는 문제이기 때문에 행과 열을 나누어줄 필요가 없고 나머지는 똑같다.

 

 

여담) 내 풀이가 파이썬 기준 성능 1위가 되었다.