[BOJ 2414] 게시판 구멍 막기

문제

---

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

풀이

---

돌맹이 제거와 비슷하지만 이 문제가 조금 더 구현할 게 있다.

행, 열 방향으로 각각 연속한 것들을 하나의 노드로 묶어줘야 한다.

코드

---

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

idx = 0
for i in range(n):
    for j in range(m):
        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)