백준 9525 / C++

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

9525번: 룩 배치하기

 

[ 풀이 ] 

X를 기준으로 열과 행들이 나뉜다. 나뉜 열과 행들에 각각 순번을 매겨주자. 

한 칸에 룩을 놓는 행위는 그 칸의 행과 열을 매칭시켜준다고 볼 수 있다. 

또한 룩은 서로 공격할 수 없으므로 한 행에 대해 한 열을 택했다면, 다른 행은 이 열을

택할 수 없으므로 결국 이분매칭에서 최대매칭수를 찾아주면 된다. 

구현이 좀 복잡한데 map으로 각 칸 (i,j)에 대해 연결여부를 체크해주면 된다. 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
vector<int>g[11111];
int n, par[11111], vis[11111];
char a[101][101];
int temp[2][101][101];
map<pair<int, int>, int> mp;
#define FOR(i,n) for(int i=1;i<=n;i++)

int match(int x) {
	for (int nx : g[x]) {
		if (vis[nx])continue;
		vis[nx] = 1;
		if (!~par[nx] || match(par[nx])) {
			par[nx] = x;
			return 1;
		}
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	FOR(i, n) FOR(j, n) cin >> a[i][j];
	int ridx = 1, cidx = 1;
	// 열 인덱스 
	FOR(i, n) {
		FOR(j, n) {
			if (a[i][j] == '.') temp[0][i][j] = cidx;
			if (a[i][j] == 'X' || j == n) cidx++;
		}
	}
	// 행 인덱스 
	FOR(i, n) {
		FOR(j, n) {
			if (a[j][i] == '.') temp[1][j][i] = ridx;
			if (a[j][i] == 'X' || j == n) ridx++;
		}
	}
	FOR(i, n) {
		FOR(j, n) {
			int x = temp[0][i][j];
			int y = temp[1][i][j];
			// 행과 열 인덱스끼리 연결 
			if (!mp[{x, y}]) {
				g[x].push_back(y);
				mp[{x, y}] = 1;
			}
		}
	}
	int ans = 0;
	memset(par, -1, sizeof(par));
	FOR(i, cidx) {
		memset(vis, 0, sizeof(vis));
		ans += match(i);
	}
	cout << ans;
}