[파이썬] 1760 N-Rook

def bimatch(num):
    if visited[num]:
        return False
    visited[num] = 1
    for g in graph[num]:
        if selected[g] == -1 or bimatch(selected[g]):
            selected[g] = num
            return True
    return False

n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
row_board = [[0] * m for _ in range(n)]

count = 0
for i in range(n):
    count += 1
    check = 0
    for j in range(m):
        if board[i][j] < 2:
            row_board[i][j] = count
            check = 1
        if board[i][j] == 2 and check:
            count += 1
            check = 0

l = count + 1
graph = [[] for _ in range(l)]
count = 0
for i in range(m):
    count += 1
    check = 0
    for j in range(n):
        if board[j][i] == 0:
            graph[row_board[j][i]].append(count)
            check = 1
        if board[j][i] == 2 and check:
            count += 1
            check = 0

graph += [[] for _ in range(max(0, count))]
l = len(graph)
selected = [-1] * (l)
ans = 0
for i in range(l):
    visited = [0] * l
    if bimatch(i):
        ans += 1
print(ans)

 

이분 매칭

1. row를 기준으로 넘버링 / 벽(board가 2)과 row를 기준으로 count를 row_board에 할당

2. count 만큼 graph 생성

3. column을 기준으로 넘버링 / 빈 격자(board가 0)일 경우 row_board의 값과 현재 count를 묶어 graph에 추가

4. count 만큼 그래프 길이 추가

5. 이분매칭