[C] Backjoon 17471 게리맨더링

백준 17070번 문제는 게리맨더링이다. 문제에 대한 내용과 그림 등은 백준에서 직접 확인하길 바란다. 복잡하지 않은 알고리즘 문제에서는 바로 코딩을 해도 되지만, 문제를 분석하고 어떤 함수와 요소들을 활용하여 문제를 해결할지 고민하고 정리하는 것이 시행착오를 줄일 수 있다.

문제 요구 사항을 분석하면 아래와 같다.

1. 2개의 집단으로 선거구를 구분해야 한다.
2. 각 구역은 연결되어있어야 한다.
3. 2를 구현하기 위해, 그래프 형태의 DFS를 구현한다.
4. 두 선거구가 확정되면, 각 선거구 인구의 합을 계산해야한다.
5. 각 선거구 인구 합의 차이를 최소로 하는 조합을 찾아야한다.

문제 상세 요건 및 분석사항은 아래와 같다.

1. 선거구는 적어도 하나의 구역을 포함해야한다.
2. 다른 문제들에 비해 시간 제한이 짧은 편이므로 순열이 아닌 조합을 사용해야한다.

#include <stdio.h>
#define diff(a,b) ((a>b)? a-b: b-a)

int population[11];
int graph[11][11];
int p_visit[11];
int g_visit[11];
int graph_sum;
int g_min = 99999;


void DFS(int v, int N) {
	if (g_visit[v] == 0) {
		g_visit[v] = 1;
		graph_sum = population[v];
	}
	for (int i = 1; i <= N; i++) {
		if (g_visit[i] == 1) continue;
		if (graph[v][i] == 0) continue;
		g_visit[i] = 1;
		graph_sum += population[i];
		DFS(i, N);
	}
}

void copy_visit(int N) {
	for (int i = 1; i <= N; i++) {
		g_visit[i] = p_visit[i];		
	}
}

void reverse_visit(int N) {
	for (int i = 1; i <= N; i++) {
		g_visit[i] = 1 - p_visit[i];
	}
}

int visit_check(int N) {
	for (int i = 1; i <= N; i++) {
		if (g_visit[i] == 0) return 1;
	}
	return 0;
}


void divide_func(int N) {
	graph_sum = 0;
	reverse_visit(N);
	for (int i = 1; i <= N; i++) {
		if (g_visit[i] == 0){
			DFS(i, N);
			break;
		}
	}
	if (visit_check(N)) return;    
	int temp = graph_sum;

	copy_visit(N);
	for (int i = 1; i <= N; i++) {
		if (g_visit[i] == 0){
			DFS(i, N);
			break;
		}
	}
	if (visit_check(N)) return;
	int temp2 = graph_sum;

	int min = diff(temp, temp2);
	if (g_min > min) g_min = min;
}

void combi(int v, int n, int N) {

	if (n == N) {
		divide_func(N);
		return;
	}
	else if (n > 1) {
		divide_func(N);
	}
	for (int i = v; i <= N; i++) {
		if (p_visit[i] == 1) continue;
		p_visit[i] = 1;
		combi(i, n + 1, N);
		p_visit[i] = 0;		
	}
}


int main() {

	int N;
	scanf("%d", &N);
	
	for (int i = 1; i <= N; i++) {
		scanf("%d", &population[i]);
	}
	for (int i = 1; i <= N; i++) {
		int u;
		scanf("%d", &u);
		for (int j = 0; j < u; j++) {
			int v;
			scanf("%d", &v);
			graph[i][v]=1;
			graph[v][i] = 1;
		}		
	}

	combi(1, 1, N);

	if (g_min == 99999) printf("-1");
	else printf("%d", g_min);

	return 0;
}