[백준] 2414 게시판 구멍 막기

문제

N×M 모양의 게시판에 구멍이 뚫려 있다. 이를 폭이 1인 테이프를 이용하여 막으려 한다. 테이프의 길이는 무한하다고 생각해도 좋지만, 테이프를 끊어내는 횟수를 최소로 하려 한다. 테이프를 붙일 때에는 구멍이 뚫려 있지 않은 부분을 막아서는 안 된다. 하지만 테이프가 한 번 붙은 곳에 테이프를 또 붙여도 된다. 또한, 테이프를 붙일 때에는 가로나 세로로 붙이는 경우만 허용한다.

입력

첫째 줄에 N, M(1 ≤ N, M ≤ 50)이 주어진다. 다음 N개의 줄에는 M개의 문자로 게시판의 모양이 주어진다. 각각의 문자는 붙어 있으며, 구멍이 없는 부분은 '.', 구멍이 있는 부분은 '*'으로 주어진다.

출력

첫째 줄에 테이프를 끊어 내는 횟수의 최솟값을 출력한다.

 

 

 

문제는 모든 구멍을 테이프로 막는 최소의 수를 구하면 됩니다.

 

사실 모든 가로줄만 붙인다면 모든 게시판의 구멍을 채울 수 있습니다 (5개)

하지만 세로줄을 이용한다면 5개를 안쓰고도 모든 게시판의 구멍을 채울 수 있습니다.

 

이는 최소 버텍스 문제로....

이분매칭의 수가  모든 정점을 채울 수 있는 최소 정점의 수와 같기때문에

 

이분매칭만으로 답을 구할 수 있습니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL)
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 };

int N, M, cnt, v[2502], d[2502], n, R, C ,l[52][52];
vi adj[2502];
char c, mp[52][52];
bool dfs(int k) {
	for (auto r : adj[k]) {
		if (v[r])continue;
		v[r] = 1;
		if (!d[r] || dfs(d[r])) {
			d[r] = k;
			return true;
		}
	}
	return false;
}
int main() {
	FAST;
	cin >> N >> M;
	rep(i, N)rep(j, M)cin >> mp[i][j];

	rep(i, N) {
		bool f = false;
		rep(j, M) {
			if (mp[i][j] == '*') {
				if (!f)R++;
				l[i][j] = R;
				f = true;
			}
			else {
				f = false;
			}
		}
	}
	rep(i, M) {
		bool f = false;
		rep(j, N) {
			if (mp[j][i] == '*') {
				if (!f)C++;
				adj[l[j][i]].push_back(C);
				f = true;
			}
			else f = false;
		}
	}
	REP(i, R) {
		mset(v);
		if (dfs(i))cnt++;
	}
	cout << cnt;

}