[BOJ 2570] 비숍 2

문제

---

https://www.acmicpc.net/problem/2570

풀이

---

룩 배치하기의 비숍 버전이다.

1. 기본적으로 좌하단 방향으로 훑으면서 장애물 없이 연속된 위치들을 한 노드로 묶는다.

2. 좌상단에도 비숍이 놓일 수 있으면 그 지점이 나타내는 노드와 연결한다.

코드

---

import sys


def dfs(cur):
    visit[cur] = 1
    for nxt in graph[cur]:
        if not b[nxt] or (not visit[b[nxt]] and dfs(b[nxt])):
            b[nxt] = cur
            return 1
    return 0


n = int(sys.stdin.readline())

board = [[1] * n for _ in range(n)]
for _ in range(int(sys.stdin.readline())):
    x, y = map(int, sys.stdin.readline().split())
    board[x - 1][y - 1] = 0

index = [[0] * n for _ in range(n)]
graph = [[]]

idx = 0
for s in range(2 * n - 1):
    for i in range(max(0, s - n + 1), min(s + 1, n)):
        j = s - i

        if board[i][j]:
            if i and (j < n - 1) and index[i - 1][j + 1]:
                if i and j and index[i - 1][j - 1]:
                    graph[-1].append(index[i - 1][j - 1])
                    index[i][j] = index[i - 1][j - 1]
                else:
                    idx += 1
                    graph[-1].append(idx)
                    index[i][j] = idx
            else:
                if i and j and index[i - 1][j - 1]:
                    graph.append([index[i - 1][j - 1]])
                    index[i][j] = index[i - 1][j - 1]
                else:
                    idx += 1
                    graph.append([idx])
                    index[i][j] = idx

b = [0] * (idx + 1)
ans = 0
for i in range(1, len(graph)):
    visit = [0] * len(graph)
    ans += dfs(i)

print(ans)