[BOJ 9525] 룩 배치하기

문제

---

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

풀이

---

게시판 구멍 막기와 동일한 문제이다.

코드

---

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 = [sys.stdin.readline().strip() for _ in range(n)]
index = [[0] * n for _ in range(n)]
graph = [[]]

idx = 0
for i in range(n):
    for j in range(n):
        if board[i][j] == '.':
            if j and index[i][j - 1]:
                if i and index[i - 1][j]:
                    graph[-1].append(index[i - 1][j])
                    index[i][j] = index[i - 1][j]
                else:
                    idx += 1
                    graph[-1].append(idx)
                    index[i][j] = idx
            else:
                if i and index[i - 1][j]:
                    graph.append([index[i - 1][j]])
                    index[i][j] = index[i - 1][j]
                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)