[C] 백준 17471번 : 게리맨더링

 

오늘은 새로운 A형 기출문제를 풀어보았습니다!

분명 골드 5 문제였는데,, 여태 풀었던 문제 중에 제일 머리가 아팠답니다..^^ 심한 욕 

저는 오늘 2단계에 걸쳐 문제를 풀었습니다.

1. 어떻게 풀지 고민하기

2. 코드로 작성하기

 

백준 17471번

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

17471번: 게리맨더링

 

1. 어떻게 풀지 고민하기

 

저는 이 문제를 풀려고 여러 가지 방법을 시도해보았습니다.

처음에는 N까지의 부분집합을 쫙 구하여 구역을 나누고,

구역 별로 무리가 지어지는지(선거구로 나눌 수 있는지)를 확인하려 했습니다.

하지만,, 이것을 구현하자니 머리가 좀 아파서^^ㅜ 다른 방법들을 더 고민해보았습니다.

node들 간의 거리를 각각 구해보기도 하고 for문을 와장창 돌려보는 등등 다양한 방법을 시도해보았지만,

채점하면 오답으로 나오더라고요ㅠㅠ

그래서 결국엔 처음 생각했던 방식으로 해결해보기로 했습니다.

바로 조합 + Connected Component (+DFS)를 사용하는 것입니다!

.

조합은 A, B 구역을 어떻게 나눌지를 선정하는 데 사용합니다.

즉, 1~N까지의 구역 중 x개를 선택하는 것입니다.

(선택한 쪽은 A구역, 안 한 쪽은 B구역이라고 생각)

좀 더 쉽게 말하면 그냥 {1,2, ... , N}이라는 집합이 있고, 이것의 부분집합을 구한다고 생각하시면 됩니다!

.

Connected Component는 나누어진 A와 B구역이 선거구로 나누어질 수 있는지를 확인합니다.

즉, A와 B가 모두 하나의 덩어리로 이루어졌는지를 검사하는 것입니다.

이때 저는 DFS(깊이 우선 탐색) 방식을 이용하였습니다.

DFS 구현을 위해 별도의 stack도 생성하였습니다.

 

-------------------------------------------------------------------------------------------------------------------

 

 

2. 코드로 작성하기

#define _CRT_SEUCRE_NO_WARNINGS
#include <stdio.h>
#define MAX 10

int N, min = 100 * MAX + 1;
// 입력 받는 배열
int people[MAX + 1];
int connect[MAX + 1][MAX + 1];

// 조합 구하기
int comb[MAX + 1];

// connected component인지 확인할 때 사용
int cnt;
int visited[MAX + 1];
int stack[MAX];
int top = 0;

// stack과 관련된 함수들
int isEmpty() {
	return top == 0;
}
void push(int x) {
	visited[x] = cnt;
	stack[++top] = x;
}
int peek() {
	return stack[top];
}
int pop() {
	return stack[top--];
}

// visited 배열 초기화
void init_visited() {
	for (int i = 1; i <= N; i++)
		visited[i] = 0;
}

// DFS 깊이 우선 탐색
void dfs(int i) {
	push(i);
	int output, flag=0;
	while (!isEmpty()) {
		flag = 0;
		output = peek();
		for (int j = 1; j <= N; j++)
			if (connect[output][j] == 1 && comb[output] == comb[j]) {
				if (visited[j] == 0) {
					push(j);
					flag++;
					break;
				}
			}
		if (flag == 0)
			pop();
	}
}

// connected component인지 검사
int isGroup() {
	cnt = 0;

	int except_cnt = 0;
	for (int i = 1; i <= N; i++) {
		if (comb[i] == 1) {
			except_cnt++;
			break;
		}
	}
	if (except_cnt == 0)
		return 0;

	for (int i = 1; i <= N; i++) {
		if (visited[i] == 0) {
			cnt++;
			dfs(i);
		}
	}
	for (int i = 1; i <= N; i++) {
		if (visited[i] > 2)
			return 0;
	}
	return 1;
}

// 인구 수 차이 계산
void calculate() {
	int a_sum = 0, b_sum = 0, gap;
	for (int i = 1; i <= N; i++) {
		if (visited[i] == 1) // A그룹
			a_sum += people[i];
		else if (visited[i] == 2) // B그룹
			b_sum += people[i];
	}
	if (a_sum > b_sum)
		gap = a_sum - b_sum;
	else
		gap = b_sum - a_sum;
	if (gap < min)
		min = gap;
}

// 조합 구하기
void combination(int n, int r) {
	// combination 함수 종료 -> 무리 찾기
	if (r==0) {
		if (isGroup()) 
			calculate();
		init_visited();
	}
	else {
		comb[r] = 0; // A구역
		combination(n, r - 1);
		comb[r] = 1; // B구역
		combination(n, r - 1);
	}
}

int main() {

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

	int num, input;
	for (int i = 1; i <= N; i++) {
		scanf("%d", &num);
		for (int j = 0; j < num; j++) {
			scanf("%d", &input);
			connect[i][input] = 1;
		}
	}

	combination(N, N);

	if (min == 100 * MAX + 1)
		printf("%d\n", -1);
	else
		printf("%d\n", min);

	return 0;
}

 

제가 작성한 코드는 위와 같습니다.

조금 복잡하게 보일 것 같아서 함수의 실행 순서에 대해 간략하게 설명드리겠습니다.

우선 combination이라는 함수를 통해 ① 부분 집합을 구해줍니다.

저는 이때 재귀 함수를 사용하여 맨 오른쪽 index(index=N)부터 1을 채워나가는 방식을 사용하였습니다.

그리고 combination 함수의 종료 조건에 다다르면 (index=0)

.

② connected component 조건을 만족하는지 확인합니다.

comb 배열이 0 -> A 구역

comb 배열이 1 -> B 구역

이라고 나누어 생각하고, 이 두 구역이 무리가 지어지는지를 확인하면 됩니다.

isGroup 함수에서는 dfs 함수를 사용하여 visited 배열을 채워줍니다.

(except_cnt를 구하는 부분은 공집합일 때를 거르기 위해 넣은 예외조건입니다.)

visited에서는 기존에 사용했던 0과 1(true, false)을 넣는 방식이 아닌 cnt를 넣는 방식을 활용하였습니다.

이렇게 되면 cnt로 무리를 구분 짓을 수 있습니다.

(Ex. 무리가 2개 있다면 무리 1은 visited 값 1, 무리 2는 visited 값 2)

그렇게 visited 배열을 채운 후 무리가 2개 이상이지 않다면,

true를 return 하고

.

③ 인구 차이를 계산(calculate함수 활용)해줍니다!

이 과정을 반복하여 인구 차이의 최솟값인 min을 구할 수 있습니다.

 

-------------------------------------------------------------------------------------------------------------------

 

 

부분 집합 구하기나 DFS 방식은 너무 예전에 배운 내용이라 기억이 가물가물하여,

자료구조 책을 조금 참고하였습니다!

오랜만에 자료구조 책을 펴니 굉장히 낯선 개념이 많더라구요...

공부를 좀 더 열심히 해야 할 것 같습니다.

그리고 함수 안에 함수를 겹겹이 사용하다 보니 가독성이 조금 떨어지는 것 같네요ㅜㅜ

혹시 이해 안 가는 부분이 있다면 댓글 달아주세요 :)