boj, 백준) 17471. 게리맨더링(C / C++)

1. 문제 링크

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

17471번: 게리맨더링

2. 문제 개요

 선거구를 조건에 알맞게 2개로 나누되, 각 인구 차가 최소가 되는 값을 구하기.

 

3. 문제 힌트

   선거구를 두그룹으로 나누기 -> DFS

   ex) [1,2,3,4,5,6]이라면, 1개/5개 or 2개/4개 or 3개/3개 의 경우가 있다.

 

   각 선거구가 연결되었는지 확인 -> BFS

 

4. 문제 풀기

 각 선거구를 나누기 위해 DFS를 반복문에 넣어 main함수에서 실행한다.

n개의 선거구가 있다면, (1, n-1) , (2, n-2)... 순으로 dfs함수를 실행함. 

 

DFS로 조합을 구현하여 두개의 그룹으로 나누고, 각 그룹의 노드 1개씩을 Queue에 넣어 BFS를 한다.

방문하지 않은 노드가 있다면 Return 하여 무시하고, 모두 방문하여 선거구들이 적절히 나뉘어있고, 모두 연결되어있음을 알게 되면

합을 구해서 최소값을 구한다.

 

알고리즘만 바로 생각나면 큰 문제없이 해결할 수 있는 문제라고 생각한다.

(그리고 코드에서는 DFS를 1~n까지 반복했지만, n/2까지 반복해도 괜찮을 듯해 보인다. (n이 짝수인 경우만. 홀수는 +1) 맞나..?)

 

5. 코드

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n;
int val[11];
vector<int> v[11];
int groupsrc[11];
int ret = 0x7fffffff;

struct COORD {
	int vertex;
	int g;
};


void dfs(int depth, int start, int limit)
{
	if (depth == limit)
	{
		int group[11];
		for (int i = 1; i <= n; i++)
			group[i] = 2;
		for (int i = 0; i < limit; i++)
			group[groupsrc[i]] = 1;

		int g1, g2;
		g1 = groupsrc[0];
		for (int i = 1; i <= n; i++)
			if (group[i] == 2)
			{
				g2 = i;
				break;
			}



		bool visited[11] = { false, };
		queue<COORD> q;
		COORD s1, s2;
		s1.vertex = g1, s1.g = 1;
		s2.vertex = g2, s2.g = 2;
		visited[s1.vertex] = visited[s2.vertex] = true;
		q.push(s1), q.push(s2);

		while (!q.empty())
		{
			COORD cur = q.front(); q.pop();

			int len = v[cur.vertex].size();

			for (int dir = 0; dir < len; dir++)
			{
				COORD next;
				next.vertex = v[cur.vertex][dir];
				next.g = cur.g;

				if (visited[next.vertex] == false && group[next.vertex] == cur.g)
				{
					visited[next.vertex] = true;
					q.push(next);
				}

			}
		}

		for (int i = 1; i <= n; i++)
			if (visited[i] == false)
				return;

		int sum1 = 0, sum2 = 0;
		for (int i = 1; i <= n; i++)
		{
			if (group[i] == 1)
				sum1 += val[i];
			else if (group[i] == 2)
				sum2 += val[i];
		}

		int temp = abs(sum1 - sum2);

		ret = min(ret, temp);

		return;
	}
	for (int i = start; i <= n; i++)
	{
		groupsrc[depth] = i;
		dfs(depth + 1, i + 1, limit);
		groupsrc[depth] = 0;
	}
	return;
}
int main(void)
{
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
		scanf("%d", &val[i]);

	
	for (int i = 1; i <= n; i++) {
		int num;
		scanf("%d", &num);
		for (int j = 0; j < num; j++)
		{
			int to;
			scanf("%d", &to);
			v[i].push_back(to);
		}
	}

	for (int i = 1; i<n; i++)
		dfs(0, 1, i);

	if (ret == 0x7fffffff)
		printf("-1");
	else
		printf("%d", ret);
	return 0;
}

6. 결과 사진

지적, 댓글 언제나 환영입니다~