백준 17471 C++

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

17471번: 게리맨더링

 

이 문제에서 비트마스킹을 어떻게 사용할지는 큰 고민을 하지 않았다.

하지만 고민이 깊어진 것은 선거구가 모두 연결되어있는지? 이걸 어떻게 알것인가였다.

처음에는 각 선거구를 vector로 저장해서 visited로 해당 선거구vector에 있는 요소가 다 들어왔는지 체크하려고 했다.

아.. 근데 생각보다 복잡하게 코드가 흘러가서 파기하고 dfs로 돌며 모든 노드를 방문하였는지로 생각하였다.

 

결국 시작점이 0선거구 1선거구로 나눠져있으니 각 선거구가 한 지점에서 시작하고 각 선거구가 연결되어있다면 모든 선거구를 돌것이다라는 생각을 하였고 checkN으로 Node갯수를 세어서 확인하였다.

 

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int n; int checkN = 0; int p0 = 0; int p1 = 0;
int result = 987654321;
int p[20]; int comp[20]; int visited[20];
vector<vector<int>> g(20);


void Init()
{
	fill(&comp[0], &comp[0] + 20, 0);
	fill(&visited[0], &visited[0] + 20, 0);
	checkN = 0; p0 = 0; p1 = 0;
}

void dfs(int index, int num)
{	
	visited[index] = 1;
	checkN++;		//방문했던 노드 수를 올려줌
	//cout << "index : " << index << "\n";
	if (num == 0) {
		p0 += p[index];		//인구수를 더해준다.
		//cout << "index : " << index << "   p0 :" << p0 << "\n";
	}
	else {
		p1 += p[index];
		//cout << "i : " << index << "   p1 :" << p1 << "\n";
	}

	for (int i : g[index]) {		//i -> index와 연결된 노드들을 순차적으로 나타냄
		if (comp[i] != num) continue;	//i노드가 같은 선거구가 아니면 continue
		if (visited[i]) continue;	//i노드가 이미 방문한 노드라면 continue

		//if (num == 0) {
		//	p0 += p[i];		//인구수를 더해준다.
		//	cout << "i : " << i << "   p0 :" << p0  <<"\n";
		//}
		//else{
		//	p1 += p[i];
		//	cout << "i : " << i << "   p1 :" << p1 << "\n";
		//}

		dfs(i, num);
	}
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {		//인구 수 입력
		int t; cin >> t;
		p[i] = t;
	}

	for (int i = 1; i <= n; i++) {				//gragh 제작
		int loop; cin >> loop;
		for (int j = 1; j <= loop; j++) {
			int t; cin >> t;
			g[t].push_back(i);
			g[i].push_back(t);
		}
	}

	//g[i]가 제대로 들어갔는지 확인 -> 오류 확인 j<loop였음.
	//for (int i = 1; i <= n; i++) {
	//	cout << i<<" in ";
	//	for (int j : g[i]) {
	//		cout << j << " ";
	//	}
	//	cout << "\n";
	//}

	for (int i = 1; i < (1 << n) - 1; i++) {
		int count = 1; int index0 = 0, index1 = 0;
		Init();

		for (int j = 1; j < (1 << n); j = j*2) {
			if (i & j) {
				comp[count] = 1;
				index1 = count;			//count -> Node Numder
			}
			else {
				index0 = count;
			}
			count++;
		}

		//cout << "num = 0\n";
		dfs(index0, 0);
		//cout << "num = 1\n";
		dfs(index1, 1);

		if (n != checkN) continue;

		int subResult = abs(p0 - p1);


		//cout << "i : " << i << "    subResult : " << subResult << "\n";
		//cout << "p0 : " << p0 << "   p1 : " << p1 << "\n\n";

		result = min(subResult, result);
	}

	if (result != 987654321) {
		cout << result;
	}
	else cout << -1;
}

 

 

이번에 좀 다른 방식으로 한번 더 풀어보았다. 대충 느낌은 비슷하긴 한거 같다.

#include <bits/stdc++.h>

using namespace std;

int n; int result = 987654321;
vector<int> p;		//각 지역구 마다의 인구수
int bc, rc;
int bs, rs;
int ps;			//총 인구수
int bp, rp;
int visited[11];
int arr[11];
vector<vector<int>> link(11);

void Init() {
	bc = 0; rc = 0;
	bs = -1; rs = -1;
	bp = 0; rp = 0;
	fill(&visited[0], &visited[0] + 11, 0);
	fill(&arr[0], &arr[0] + 11, 0);
}

void dfs(int index, bool isBlue)
{
	visited[index] = 1;
	if (isBlue) bp += p[index];
	else rp += p[index];

	for (auto i : link[index]) {
		if (visited[i]) continue;		//방문했다면 다시 안간다.
		//cout << " link[index] in : " << i << "\n";

		if (isBlue && arr[i] == 1) {			//지금 파란색 지역구를 돌고 있으면서 i지역구 또한 파란색 지역구로 선정된 경우라면
			visited[i] = 1;
			dfs(i, isBlue);
		}
		else if(!isBlue && arr[i] == 0)		//지금 빨간색 지역구를 돌고 있으면서 i지역구 또한 빨간색이다.
		{
			visited[i] = 1;
			dfs(i, isBlue);
		}
	}
}

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

	cin >> n;

	for (int i = 0; i < n; i++) {		//인구 수 입력
		int t; cin >> t;
		ps += t;
		p.push_back(t);
	}

	for (int i = 0; i < n; i++) {			//연결 되어있는걸 나타냄.
		int c; cin >> c;
		for (int j = 0; j < c; j++) {
			int temp; cin >> temp;
			link[i].push_back(temp-1);			//i 구역에 연결되어 있는 애들 모두 넣는다.
		}
	}

	for (int i = 1; i < (1 << n)-1; i++) {			//모든 경우의 수에 대해서 계산한다.
		Init();
		
		for (int j = 0; j < n; j++) {
			if (i & (1 << j)) {		//i수에 대해서 j번째 비트가 켜져있다면 
				if (bs == -1) bs = j;
				arr[j] = 1;
			}
			else {
				if (rs == -1) rs = j;
			}
		}

		//cout << "i : " << i << "\n";

		dfs(bs, true);
		//cout << "end 1" << "  rs : " << rs << "   bs : " << bs;
		dfs(rs, false);

		if (bp + rp == ps) {		//모든 지역구를 다 돌았다.
			result = min(result, abs(bp - rp));
		}
	}

	if (result == 987654321) {
		cout << -1;
	}
	else {
		cout << result;
	}
}

 

이번에도 다르게 풀어봤는데

비트마스킹에서 너무 temp & (1<<i)가 true로 나오는게 익숙해서
if(temp & (1<<i)) == 1)로 했다가 넘어가는게 이상해서 다시 보니까 1처럼 숫자로 하면 안된다는 것을 깨닫고 bool로 해서 넘겼다.

#include <bits/stdc++.h>

using namespace std;

int n, minResult = 987654321;
int tempIndex, tempSum;
int visited[20];
vector<int> populars;
vector<int> Sums;
vector<vector<int>> Links(20);

void FindLink(int vilage, bool isOn)
{
	visited[vilage] = 1;
	tempSum += populars[vilage];

	for (int i : Links[vilage]) {
		//cout << "In i:  " << i << "\n";
		if (visited[i]) continue;

		//if((temp & (1<<i)) == 1)로 하면 안되네.. 이게 1이 아니라 2든 4든 8이든 될 수가 있어서 안됐구나

		if (isOn && (tempIndex & (1 << i))) {
			//cout << "On Find Link Vilage : " << i << "\n";
			FindLink(i, isOn);
		}
		else if (!isOn && !(tempIndex & (1 << i))) {
			//cout << "Off Find Link Vilage : " << i << "\n";
			FindLink(i, isOn);
		}
	}
}

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

	cin >> n;

	int pop;
	for (int i = 0; i < n; i++) {				//인구 수 입력
		cin >> pop;
		populars.push_back(pop);
	}

	int linkNum;
	for (int i = 0; i < n; i++) {						//link확인 & 잘들어가는 것 확인 완료
		cin >> linkNum;
		int link;
		for (int j = 0; j < linkNum; j++) {
			cin >> link;
			Links[i].push_back(link - 1);			//link - 1을 해줘야한다. 만약 link가 1이면 0번째 비트와 비교해서 계산할 것이기 때문이다.
		}
	}

	for (int i = 1; i < ((1 << n) - 1); i++) {
		fill(&visited[0], &visited[0] + 20, 0);
		Sums.clear();
		tempIndex = i; tempSum = 0;
		//cout << "i : " << tempIndex << "\n";
		
		for (int j = 0; j < n; j++) {
			if (visited[j]) continue;

			tempSum = 0;
			if ((tempIndex & (1 << j)) == 0) {		//비트가 꺼져있다면
				//cout << "Bit Off Start Vilage : " << j << "\n";
				FindLink(j, false);
				Sums.push_back(tempSum);
			}
			else {
				//cout << "Bit On Start Vilage : " << j << "\n";
				FindLink(j, true);
				Sums.push_back(tempSum);
			}
		}

		if (Sums.size() == 2) {
			int tempSumsResult = abs(Sums[0] - Sums[1]);
			//cout << "Sums[0] : " << Sums[0] << "  Sums[1] : " << Sums[1] << "\n";
			//cout << "Sum Sub Result : " << tempSumsResult;
		
			minResult = min(minResult, tempSumsResult);
		}
		else {
			//cout << "Sums Size : " << Sums.size();
		}
		//cout << "\n";
	}

	if (minResult == 987654321) {
		cout << -1;
	}else{
		cout << minResult;
	}
}