[백준] 1574 룩 어택

문제

세준이는 N개의 빈 칸이 있는 R×C크기의 체스판을 가지고 있다. 빈 칸에는 룩을 놓을 수 없지만, 공격을 할 수 있는지 없는지에는 영향을 미치지 않는다. 즉, 빈 칸을 사이에 두고도 공격을 할 수 있다.

R×C크기의 체스판에 최대 몇 개의 룩을 서로 공격하지 않게 놓을 수 있는지 구하는 프로그램을 작성하시오. 룩은 자기와 같은 행 또는 열에 다른 룩이 있으면 잡을 수 있다.

입력

첫째 줄에 체스판의 크기 R과 C가 주어지고, 빈 칸의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 빈 칸의 좌표가 주어진다. 좌표는 (행, 열)의 형태로 주어지고, 가장 윗 행은 1번 행이고, 가장 왼쪽 열은 1번 열이다. R과 C는 300보다 작거나 같은 자연수이고, N은 600보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 최대 몇 개의 룩을 놓을 수 있는지 출력한다.

 

이분매칭 문제입니다 가로행에 대해 세로행과 매치하면 그 가로행과 세로행에는 더이상 룩을 배치할 수 없습니다.

 따라서 이분매칭을 이용해서 최대 매칭의 수를 구할 수 있습니다.

 

	#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 R, C, N, mp[301][301], ans, v[301], d[301];
	vi adj[301];
	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 >> R >> C >> N;
		int y, x;
		while (N--) {
			cin >> y >> x;
			mp[y][x] = 1;
		}
		REP(i, R)
			REP(j, C)
				if (!mp[i][j])adj[i].push_back(j);
		REP(i, R) {
			mset(v);
			if (dfs(i))ans++;
		}
		cout << ans;
	}