[BOJ 1799 // C++] 비숍

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1799번 문제인 비숍이다.
문제는 아래 링크를 확인하자.

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

1799번: 비숍

좌상단에서 우하단으로 향하는 대각선들과 우상단에서 좌하단으로 향하는 대각선들을 노드로, 비숍을 놓을 수 있는 칸에서 교차하는 두 대각선 사이의 관계를 에지로 하는 그래프를 모델링하자. 이 때, 위 그래프는 각 방향별 대각선의 집합으로 둘로 나뉘는 이분그래프가 되고 주어진 문제는 이 이분그래프에서의 최대 매칭을 찾는 문제와 같아진다.

 

최대 이분매칭을 구하는 알고리즘을 이용해 문제를 해결하자.

 

번외로, N x N (N>1) 체스판 위에 서로 교차하지 않게끔 비숍을 놓을 수 있는 최대 개수는 2N-2개와 같다는 관찰을 이용하면 브루트포스를 이용해 문제를 해결할 수도 있을 것이다.

 

아래는 제출한 소스코드이다.

#define NODE 20
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int N;
int idx1[10][10], idx2[10][10];
vector<int> G[NODE];
int visited[NODE];
int matching[NODE];

int bpfunc(int current) {
	if (visited[current]) return 0;
	visited[current] = 1;
	for (auto& node : G[current]) {
		if (matching[node] == 0) {
			matching[node] = current;
			return 1;
		}
		if (bpfunc(matching[node])) {
			matching[node] = current;
			return 1;
		}
	}
	return 0;
}

int bipartitematching() {
	int ret = 0;
	for (int i = 1; i <= N; i++) {
		memset(visited, 0, sizeof(visited));
		ret += bpfunc(i);
	}

	return ret;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			idx1[r][c] = r + c + 1, idx2[r][c] = N - r + c;
		}
	}

	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			bool x; cin >> x;
			if (x) G[idx1[r][c]].emplace_back(idx2[r][c]);
		}
	}

	N = N * 2 - 1;
	cout << bipartitematching();
}