[BOJ 20294 // C++] 에어컨 설치

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

 

이번에 볼 문제는 백준 20294번 문제인 에어컨 설치이다.
문제는 아래 링크를 확인하자.

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

20294번: 에어컨 설치

각 방들을 꼭짓점으로 나타내고, 복도나 계단 등으로 연결된 두 꼭짓점 사이에 에지를 이으면 그래프를 하나 얻을 수 있다.

 

이 그래프는 좌표의 합이 홀수냐 짝수냐에 따라 집합을 나누면 이분그래프(bipartite graph)가 됨을 알 수 있다. 좌표합이 홀수인 점과 연결된 점은 좌표합이 짝수여야 하고 역도 성립하기 때문이다.

또한, 모든 방과 "복도, 계단"이 냉방이 되게끔 하는 최소한의 에어컨을 팔아야하므로 이 문제는 구한 이분그래프의 최소 버텍스 커버(minimum vertex cover)의 크기를 구하는 문제로 바꿀 수 있다.

 

이분그래프의 최소 버텍스 커버의 크기는 최대 이분매칭(maximum bipartite matching)의 크기와 같으므로, 이분매칭을 이용하여 답을 구하자.

 

단, 에지로 이어져있지 않은(vertex만 있는) 방은 모든 "복도, 계단"이 냉방이 되게끔 하는 최소 버텍스 커버에 포함되어있지 않은 vertex들이면서 에어컨을 설치해야하는 방이므로, 이러한 방들도 따로 세어주자.

 

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

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

struct point {
	int x, y, z;
};

bool adjacent(point p1, point p2) {
	int temp = abs(p1.x - p2.x) + abs(p1.y - p2.y) + abs(p1.z - p2.z);
	if (temp == 1) return 1;
	else return 0;
}

vector<point> ptL;
vector<point> ptR;

vector<int> G[1501];
int visited[1501];
int matching[1501];

int bipartite(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 (bipartite(matching[node])) {
			matching[node] = current;
			return 1;
		}
	}
	return 0;
}

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

	int N; cin >> N;
	for (int i = 0; i < N;i++) {
		int x, y, z; cin >> x >> y >> z;
		point temp;
		temp.x = x, temp.y = y, temp.z = z;
		if ((x + y + z) & 1) ptL.push_back(temp);
		else ptR.push_back(temp);
	}

	int ans = 0;
	
	int L = ptL.size(), R = ptR.size();
	for (int r = 0; r < R; r++) {
		bool chk = 0;
		for (int l = 0; l < L; l++) {
			if (adjacent(ptL[l], ptR[r])) {
				G[l + 1].push_back(r + 1);
				chk = 1;
			}
		}
		if (chk) continue;
		ans++;
	}

	for (int i = 1; i <= L; i++) {
		if (G[i].empty()) {
			ans++;
			continue;
		}
		memset(visited, 0, sizeof(visited));
		ans += bipartite(i);
	}

	cout << ans;
}