백준 17471번 게리맨더링 문제 풀이

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

17471번: 게리맨더링

 

올라온 지 얼마 안된 따끈따끈한 문제이다.

 

일단 대충 문제만 보면 그래프 문제에, 좀 빡새보이는데

 

문제 제한을 보면 N값이 2~10로 매우 작다.

 

 

이러한 점을 고려해서 모든 케이스를 고려하는 브루트 포스(Brute-force) 방식으로 문제를 푼다면 시간 복잡도는 대략

 

//(O(N2^N)//)이 된다.

 

왜냐면, 구역은 N개가 있고, 각각이 A아니면 B 선거구에 속해야 한다. 

 

각각의 구역은 2가지 경우의 수가 있고, 동시에 일어날 수 있으므로 2를 N번 곱한 경우의 수, 즉 //(2^N//)가지 경우의 수가 나온다.

 

각각의 경우에, dfs나 bfs등으로 flood-fill 식으로 인접한 녀석들을 다 탐색 한 뒤, 각각의 선거구가 한 덩어리인지 확인하기 위해서는 //(N//)의 시간이 걸리므로, //(O(N2^N)//)와 같은 시간복잡도가 나오게 된다.

 

이 시간복잡도에 Worst case의 //(N=10//)을 대입하면 대략 10만정도의 값이 나오는데,

 

이는 CPU 1초에 대략 1억번 정도의 연산을 한다는 가정을 해도 0.01초 만에 해결할 수 있는 계산량이다.

 

 

구역을 2가지로 나누는 것은 비트마스킹을 이용해서 for문 하나로 해결을 했고,

 

구역이 Valid하게 나뉘었는지는 각각 dfs를 한번 씩 해서, 선거구를 모두 cover하는지를 확인했다.

 

아래는 코드이다.

 

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321

int ans;
int n;
int p[11];
vector<int> edge[11];
set<int> visit;
void dfs(int v, set<int>& s) {
	for (int next : edge[v]) {
		if (visit.find(next) == visit.end() && s.find(next) != s.end()) {
			visit.insert(next);
			dfs(next, s);
		}
	}
}
bool is_equal(set<int>& a, set<int>& b) {
	if (a.size() != b.size()) return false;
	set<int>::iterator p1 = a.begin();
	set<int>::iterator p2 = b.begin();
	for (int i = 0; i < a.size(); i++) {
		if (*p1 != *p2) return false;
		p1++;
		p2++;
	}
	return true;
}
void check(int bit) {
	set<int> a, b;
	int aval, bval;
	aval = bval = 0;
	for (int i = 0; i < n; i++) {
		int v = (1 << i);
		if (bit & v) {
			a.insert(i);
			aval += p[i];
		}
		else {
			b.insert(i);
			bval += p[i];
		}
	}
	//if (a.size() == 0 || b.size() == 0) return;

	visit.clear();
	visit.insert(*a.begin());
	dfs(*a.begin(), a);
	if (is_equal(visit, a) == false) return;

	visit.clear();
	visit.insert(*b.begin());
	dfs(*b.begin(), b);
	if (is_equal(visit, b) == false) return;
	
	ans = min(ans, abs(aval - bval));
}
int main() {
	ans = INF;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> p[i];
	for (int i = 0; i < n; i++) {
		int v; cin >> v;
		while (v--) {
			int t; cin >> t;
			edge[i].push_back(t - 1);
		}
	}
	for (int bit = 1; bit + 1 < (1 << n); bit++) {
		check(bit);
	}
	if (ans == INF) ans = -1;
	cout << ans << endl;
}

 

문제에서는 인덱스를 1부터 센다는 것을 체크를 안해서 2번 틀리긴 했다. ㅠㅠ

 

그런데 왜 기본 TC는 맞게 나오는가!