[백준] 9525 룩 배치하기

문제

체스와 관련된 문제는 처음 알고리즘을 배우기 시작할 때 부터 접하게 된다. 가장 유명한 문제로는 N-Queen 문제가 있다. 이를 변형해서 N-Rook 문제를 만들 수 있다. Rook(룩) 은 체스에서 같은 행이나 같은 열의 아무 위치로 이동할 수 있는 체스 말이다.

N × N 크기의 체스판에 룩을 최대한 많이 어떻게 배치할까? 라는 문제는 매우 쉽게 해결할 수 있다. 대각선으로 룩을 배치하면 된다.

문제를 좀 더 어렵게 만들어서, N x N 크기의 체스판에 폰이 몇 개 놓여있다. 이런 상황에서 룩을 최대 몇 개 배치할 수 있을까? 폰이 배치 되어 있으면, 룩은 폰에게 가로막혀 같은 열이나 같은 행의 모든 위치에 이동할 수 없다.

입력

첫 줄에 체스판의 크기 N이 주어진다. (1 ≤ N ≤ 100)

그리고 다음 N개의 줄에 체스판의 정보가 주어진다. '.'은 빈 칸을 의미하고, 'X'는 그 칸에 폰이 있음을 의미한다.

출력

주어진 체스판에 룩을 배치할 때, 최대 몇 개를 배치할 수 있는지 출력한다.''

 

 

(굉장히 굉장해)

폰으로 막히지 않은 공간에 대해 얼마나 많은 룩을 놓을 수 있는지 문제입니다.

룩은 가로 세로로 움직일 수 있으므로, 막히지 않은 가로와 세로가 겹치는 지점에 하나를 놓을 수 있습니다.

따라서 가로와 세로에 대해 전처리로 이분 그래프를 만들 수 있습니다.

 

예를들면

1번가로줄에는 2,4,6,7번의 세로줄이 겹쳐있고, 룩을 배치할 수 있는 4개의 후보가 있습니다.

(1,2)위치에 룩을 배치했을때,

 

2번 가로줄도 2,4,6,7의 세로줄이 겹쳐있고

2번 세로줄에 룩을 배치하려고 했지만, 1번가로줄 즉 (1,2)위치에 이미 룩이 위치하므로 놓을 수 없습니다.

 

따라서 1번가로줄은 (1,4)로 옮기고 ,2번세로줄은 (2,2)로 놓으면서 두번째 가로줄에도 룩을 놓을 수 있습니다.

 

이후도 마찬가지입니다.

따라서 이분매칭으로 문제를 해결할 수 있습니다.

#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, C, R, l[102][102], ans, v[11001], d[11001];
char mp[102][102], x;
vi adj[11000];

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() {
	cin >> N;
	rep(i, N)rep(j, N)cin >> mp[i][j];

	rep(i, N) { //가로줄 전처리
		bool f = false;
		rep(j, N) {
			if (mp[i][j] == '.') {
				if (!f)C++;
				f = true;
				l[i][j] = C;
				
			}
			else
				f = false;
		}
	}

	rep(i, N) {//세로줄 전처리, 이분그래프 생성
		bool f = false;
		rep(j, N) {
			if (mp[j][i] == '.') {
				if (!f)
				R++;
				adj[l[j][i]].push_back(R);
				f = true;
			}
			else
				f = false;
		}
	}

	REP(i, C) {
		mset(v);
		if (dfs(i))ans++;
	}
	cout << ans;
}