백준 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;
	}
}