백준2570 비숍2

작성일 | In

문제 링크

  • http://icpc.me/2570

문제 출처

  • 2007 지역 본선 중등5

사용 알고리즘

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

풀이

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


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


몇 가지 성질을 뽑아봅시다.

  1. 각 셀에서는 두 개의 경로가 만납니다.
  2. 같은 방향으로 진행되는 경로는 서로 겹치지 않습니다.
  3. 같은 경로에는 하나의 비숍만 존재해야합니다.
  4. 문제에서는 비숍 개수의 최대 개수를 물어보고 있습니다.

성질을 잘 활용해 문제를 재구성해봅시다.

  • 각각의 경로를 정점으로 잡은 뒤, 1번 성질을 활용해 만나는 경로를 간선으로 이어줍시다.
  • 2번 성질에 의해 그래프는 이분 그래프가 됩니다.
  • 3번 성질을 잘 생각해보면, 이 문제는 독립 집합 문제임을 알 수 있습니다.
  • 4번 조건에 의해 최대 독립 집합의 크기가 문제의 정답임을 알 수 있습니다.

이분 그래프에서의 최대 독립 집합은 최대 매칭의 개수와 동일합니다. 그러므로 이분 매칭을 돌려주면 답을 구할 수 있습니다.

전체 코드

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
78
79
#include <bits/stdc++.h>
using namespace std;

int n, m;
int board[111][111];
int id[111][111][2];

int dx[] = {1, 1};
int dy[] = {1, -1};
int cnt[] = {0, 0};


void makeGroup(int dir){
	int x, y;
	cnt[dir] = 0;
	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[i][j][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;
				if(id[x][y][dir]) break;
				id[x][y][dir] = cnt[dir];
			}
		}
	}
}

set<int> g[10101];
int par[10101];
bool chk[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 >> m;
	for(int i=0; i<m; i++){
		int a, b; cin >> a >> b;
		board[a][b] = 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();
}