백준 17471 게리맨더링 ❌

CJB_ny·2023년 3월 1일
0

백준

목록 보기
92/104
post-thumbnail

게리 맨더링


로직

입력을 주르륵 다 받고

비트 마스킹으로 모든 조합의 경우의 수 다 구한다.

모든 경우의 수마다 연결이 제대로 되있는지 아닌지를 확인한다음

2등분으로 제대로 나뉜다면 최소값을 구한다.

후기

문제가 이해가 안되서 입력 로직 보면서 어떤 문제인지 이해를함.

생각한 로직은 맞았는데 "연결"이 되있다, 아니다 이부분을 구현을 못했음.

강의는 둘로 쪼개서 connected component를 구해 2등분으로 나뉘었는지 확인을 하는 로직이였다.

cpp 코드

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

#define endl "\n"
const int INF = 987654321;
int n, a[11], m, temp, ret = INF, comp[11], visited[11];
vector<int> adj[11];
pair<int, int> DFS(int here, int value)
{
	visited[here] = 1;
	pair<int, int> ret = {1, a[here]};
	for (int there : adj[here])
	{
		if (comp[there] != value) continue;
		if (visited[there]) continue;
		pair<int, int> _temp = DFS(there, value);
		ret.first += _temp.first;
		ret.second += _temp.second;
	}
	return ret;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
	}
	for (int i = 1; i <= n; ++i)
	{
		cin >> m;
		for (int j = 0; j < m; ++j)
		{
			cin >> temp;
			adj[i].push_back(temp);
			adj[temp].push_back(i);
		}
	}

	for (int i = 1; i < (1 << n) - 1; ++i)
	{
		fill(comp, comp + 11, 0);
		fill(visited, visited + 11, 0);
		int idx1 = -1, idx2 = -1;
		for (int j = 0; j < n; ++j)
		{
			if (i & (1 << j))
			{
				comp[j + 1] = 1; idx1 = j + 1;
			}
			else idx2 = j + 1;
		}
		pair<int, int> comp1 = DFS(idx1, 1);
		pair<int, int> comp2 = DFS(idx2, 0);
		if (comp1.first + comp2.first == n) ret = min(ret, abs(comp1.second - comp2.second));
	}
	cout << (ret == INF ? -1 : ret) << endl;
	
	return 0;
}
profile
공부 일기장으로 변해버린 블로그 (https://cjbworld.tistory.com/ <- 이사중)

0개의 댓글