백준9525 룩 배치하기

작성일 | In

문제 링크

  • http://icpc.me/9525

문제 출처

  • 2013 Latin America Regional Contests A번

사용 알고리즘

  • 이분 매칭
  • 최대 독립 집합

풀이

체스 말 갖고 노는 문제는 격자 그래프를 의심해봐야 합니다. 격자 그래프가 나오면 이분 매칭을 의심해봐야 합니다.


위와 같은 맵이 주어진다고 합시다. 룩이 이동할 수 있는 경로를 먼저 구해야 합니다. 오른쪽으로 가는 경로와 아래로 가는 경로, 두 가지만 구해주면 됩니다.


(비숍2)와 거의 동일하게 처리한 후, 최대 독립 집합을 구해주면 됩니다.
단, 비숍2는 경로가 대각선이지만, 이 문제는 경로가 축에 평행하다는 것만 고려해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;

int n;
int board[111][111];
int id[111][111][2];
int dx[] = {1, 0};
int dy[] = {0, 1};
int cnt[] = {0, 0};

void makeGroup(int dir){
	int x, y;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(!board[i][j]) continue;
			if(id[i][j][dir]) continue;
			x = i, y = j;
			id[x][y][dir] = ++cnt[dir];
			while(1){
				x += dx[dir]; y += dy[dir];
				if(x < 1 || y < 1 || x > n || y > n) break;
				if(!board[x][y]) break;
				id[x][y][dir] = cnt[dir];
			}
		}
	}
}

set<int> g[10101];
int chk[10101];
int par[10101];

bool match(int v){
	for(auto i : g[v]){
		if(chk[i]) continue;
		chk[i] = 1;
		if(par[i] == -1 || match(par[i])){
			par[i] = v; return 1;
		}
	}
	return 0;
}

int bipartiteMatch(){
	int ret = 0;
	memset(par, -1, sizeof par);
	for(int i=1; i<=cnt[0]; i++){
		memset(chk, 0, sizeof chk);
		ret += match(i);
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			char t; cin >> t;
			if(t == 'X') board[i][j] = 0;
			else board[i][j] = 1;
		}
	}

	makeGroup(0); makeGroup(1);

	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(!board[i][j]) continue;
			int aid = id[i][j][0];
			int bid = id[i][j][1] + cnt[0];
			g[aid].insert(bid);
		}
	}

	cout << bipartiteMatch();
}