BOJ 17471 : 게리맨더링 (A형 상시)

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/2771 (상시 A형 문제집)

 

www.acmicpc.net/problem/17471

 

이후 설명 및 입/출력은 링크 참고

A형에서 그래프는 2차원 배열로 만들면 대부분 충분하다. 제시된 N이 매우 작기 때문이다.

(N이 매우 큰 그래프는 링크드 리스트를 이용해 그래프를 만들어야 한다.)

 

만약 1번 구역과 2번 구역이 인접하다면, MAP[1][2] = MAP[2][1] = 1, 그렇지 않다면 0이 된다.

people 배열에는 구역의 인구 수를 저장한다.

#define MAX (10 + 5)

int N;
int MAP[MAX][MAX];
int people[MAX];

void input()
{
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) scanf("%d", &people[i]);

	for (int i = 1; i <= N; i++)
	{
		int size;

		scanf("%d", &size);
		for (int k = 0; k < size; k++)
		{
			int in;

			scanf("%d", &in);
			MAP[i][in] = MAP[i][in] = 1;
		}
	}
}

---

구역은 조합을 이용해 나눌 수 있다.

 

위의 예제처럼 구역이 6개가 있다고 가정하자.

그러면 1 vs 5, 2 vs 4, 3 vs 3으로 경우의 수를 나눌 수 있다. (4 vs 2와 5 vs 1은 2 vs 4와 1 vs 5과 중복이다.)

 

구역을 1 vs 5로 나누는 것은, 6개의 구역 중 1개의 구역을 선택하는 경우의 수가 된다. (5는 선택되지 않은 수)

→ 1 / 2 / 3 / 4 / 5 / 6 : ₆C₁ = 6

 

2 vs 4로 나누는 경우는 6개의 구역 중 2개를 선택하면 된다.

→ (1, 2) / (1, 3) / (1, 4) / ... / (4, 5) / (4, 6) / (5, 6) : ₆C₂ = 15

 

3 vs 3으로 나누는 경우는 6개의 구역 중 3개를 선택하면 된다. 

→ (1, 2, 3) / (1, 2, 4) / (1, 2, 5) / ... / (3, 4, 6) / (3, 5, 6) / (4, 5, 6) : ₆C₃ = 20

 

조합은 N과 M (2) - 조합 코드를 참고하면 된다.

_NC₁부터 _NC_N/2까지 경우의 수를 DFS로 만들면 된다.

void DFS(int L, int start, int size)
{
	if (L == size)
	{
		//outputList(size);
		simulate(size);
		
		return;
	}

	for (int i = start; i <= N;i++)
	{
		list[L] = i;
		DFS(L + 1, i + 1, size);
	}
}

int main(void)
{
	input();

	for (int size = 1; size <= N / 2; size++) DFS(0, 1, size);

	if (MINANS == 0x7fff0000) printf("-1\n");
	else printf("%d\n", MINANS);

	return 0;
}

---

이제 list에 구역이 저장되었으니, simulate로 구역의 인구 차이를 구해보자.

 

1) DFS에서 만든 list를 보고 makeList 배열에 해당 구역을 1로 표시한다.

2) makeList가 1인 경우는 gerryA에 구역을 저장하고, 0인 경우는 gerryB에 구역을 저장한다.

   이때, 인구수는 미리 더해둔다.

3) BFS/DFS를 이용해 모든 구역이 연결되었는지 찾는다. 이 문제에서는 BFS로 구현하였다.

4) BFS 결과 A, B의 구역이 모두 연결되었다면, 2)에서 구한 sum의 차이로 MINANS를 갱신한다.

 

선택된 구역이 (1, 3, 5)라면 makeList[1, 3, 5] = 1이 되고, [2, 4, 6] = 0이 된다.

void simulate(int size)
{
	int makeList[MAX] = { 0 };
	int gerryA[MAX] = { 0 };
	int gerryB[MAX] = { 0 };
	int acnt, bcnt, sumA, sumB, diff;

	acnt = bcnt = sumA = sumB = 0;

	for (int i = 0; i < size; i++) makeList[list[i]] = 1;

	for (int i = 1; i <= N; i++)
	{
		if (makeList[i])
		{
			gerryA[acnt++] = i;
			sumA += people[i];
		}
		else
		{
			gerryB[bcnt++] = i;
			sumB += people[i];
		}
	}

	if (BFS(gerryA, acnt) == 0 || BFS(gerryB, bcnt) == 0) return;

	diff = abs(sumA - sumB);
	if (diff < MINANS) MINANS = diff;
}

 

BFS는 A 또는 B의 구역과 크기를 넘겨 받아서 연결되었는지 판단한다.

 

1) visit[구역] = 1이 되도록 표시한다. (방문해야하는 곳을 1로 표시한다.)

2) 가장 첫 번째 구역을 queue에 담고 BFS를 시작한다. 이때, 찾은 구역은 visit에서 0으로 처리해둔다.

3) MAP[out][i] = 1인 경우(구역이 연결된 경우), 아직 방문하지 않은 구역이면 queue에 담고 visit은 0으로 만든다.

4) BFS 종료 후, visit에 1이 남아있다면 모든 구역이 연결되지 않은 것이 된다. 0을 return하면 된다.

int BFS(int gerry[MAX], int cnt)
{
	int check[MAX] = { 0 };
	int queue[MAX] = { 0 };
	int rp, wp;

	for (int i = 0; i < cnt; i++) check[gerry[i]] = 1;

	rp = wp = 0;

	queue[wp++] = gerry[0];
	check[gerry[0]] = 0;

	while (wp > rp)
	{
		int out = queue[rp++];

		for (int i = 1; i <= N; i++)
		{
			if (i == out) continue;

			if (MAP[out][i] == 1 && check[i] == 1)
			{
				queue[wp++] = i;
				check[i] = 0;
			}
		}
	}

	for (int i = 1; i <= N; i++)
		if (check[i]) return 0;

	return 1;
}

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (10 + 5)

int N;
int MAP[MAX][MAX];
int people[MAX];
int list[MAX];

void input()
{
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) scanf("%d", &people[i]);

	for (int i = 1; i <= N; i++)
	{
		int size;

		scanf("%d", &size);
		for (int k = 0; k < size; k++)
		{
			int in;

			scanf("%d", &in);
			MAP[i][in] = MAP[i][in] = 1;
		}
	}
}

void outputList(int size)
{
	for (int i = 0; i < size;i++) printf("%d ", list[i]);
	putchar('\n');
}

int abs(int x)
{
	return x > 0 ? x : -x;
}

int MINANS = 0x7fff0000;

int BFS(int gerry[MAX], int cnt)
{
	int check[MAX] = { 0 };
	int queue[MAX] = { 0 };
	int rp, wp;

	for (int i = 0; i < cnt; i++) check[gerry[i]] = 1;

	rp = wp = 0;

	queue[wp++] = gerry[0];
	check[gerry[0]] = 0;

	while (wp > rp)
	{
		int out = queue[rp++];

		for (int i = 1; i <= N; i++)
		{
			if (i == out) continue;

			if (MAP[out][i] == 1 && check[i] == 1)
			{
				queue[wp++] = i;
				check[i] = 0;
			}
		}
	}

	for (int i = 1; i <= N; i++)
		if (check[i]) return 0;

	return 1;
}

void simulate(int size)
{
	int makeList[MAX] = { 0 };
	int gerryA[MAX] = { 0 };
	int gerryB[MAX] = { 0 };
	int acnt, bcnt, sumA, sumB, diff;

	acnt = bcnt = sumA = sumB = 0;

	for (int i = 0; i < size; i++) makeList[list[i]] = 1;

	for (int i = 1; i <= N; i++)
	{
		if (makeList[i])
		{
			gerryA[acnt++] = i;
			sumA += people[i];
		}
		else
		{
			gerryB[bcnt++] = i;
			sumB += people[i];
		}
	}

	if (BFS(gerryA, acnt) == 0 || BFS(gerryB, bcnt) == 0) return;

	diff = abs(sumA - sumB);
	if (diff < MINANS) MINANS = diff;
}

void DFS(int L, int start, int size)
{
	if (L == size)
	{
		//outputList(size);
		simulate(size);
		
		return;
	}

	for (int i = start; i <= N;i++)
	{
		list[L] = i;
		DFS(L + 1, i + 1, size);
	}
}

int main(void)
{
	input();

	for (int size = 1; size <= N / 2; size++) DFS(0, 1, size);

	if (MINANS == 0x7fff0000) printf("-1\n");
	else printf("%d\n", MINANS);

	return 0;
}

 

MAP을 인접한 구역을 표시하는 데 사용하였기 때문에 실제 A형에서는 MAP을 초기화를 해줘야 한다.