[백준 17471] 게리맨더링

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

17471번: 게리맨더링

#include <cstdio>
#include <list>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
int N;
int P[10 + 2];
int ans = 0x7fffffff;

std::list<int> L[10 + 2];
std::vector<int> C1;
std::vector<int> C2;

std::queue<int> Q;
int visited[10 + 2];


void input()
{
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &P[i]);
	}
	for (int i = 1; i <= N; i++) {
		int num = 0;
		scanf("%d", &num);
		for (int j = 1; j <= num; j++) {
			int city = 0;
			scanf("%d", &city);
			L[i].push_back(city);	// 노드 i에 대한 연결 리스트 만든다.
		}
	}
}

bool is_linked()
{
	// C1 선거구
	Q = {};
	memset(visited, 0, sizeof(visited));

	Q.push(C1[0]);	// 벡터의 첫번째 노드부터 탐색
	visited[C1[0]] = 1;
	int cnt1 = 1;

	while (!Q.empty()) {
		int node = Q.front();
		Q.pop();

		for (int next : L[node]) {
			if (visited[next]) continue;
			auto iter = std::find(C1.begin(), C1.end(), next);
			if (iter == C1.end()) continue;
			Q.push(next);
			visited[next] = 1;
			cnt1++;
		}
	}

	// C2 선거구
	Q = {};
	memset(visited, 0, sizeof(visited));

	Q.push(C2[0]);
	visited[C2[0]] = 1;
	int cnt2 = 1;

	while (!Q.empty()) {
		int node = Q.front();
		Q.pop();

		for (int next : L[node]) {
			if (visited[next]) continue;
			auto iter = std::find(C2.begin(), C2.end(), next);
			if (iter == C2.end()) continue;
			Q.push(next);
			visited[next] = 1;
			cnt2++;
		}
	}
	if (cnt1 == C1.size() && cnt2 == C2.size()) return true;
	return false;
}

int get_population(std::vector<int> V)
{
	int total = 0;
	for (int v : V) {
		total += P[v];
	}
	return total;
}


void DFS(int n, int c1, int c2)
{
	if (c1 > N || c2 > N) return;	// 도시는 N개까지 
	
	// 선거구는 구역을 적어도 한 개 포함해야 한다. 
	if (c1 >= 1 && c2 >= 1 && c1 + c2 == N) {
		if (!is_linked()) return;
		int city1 = get_population(C1);
		int city2 = get_population(C2);
		int sub = abs(city1 - city2);
		if (sub < ans) ans = sub;
		return;
	}



	// C1 선거구에 포함 
	// 0번부터 시작하므로 +1 해줌
	C1.push_back(n + 1);
	DFS(n + 1, c1 + 1, c2);
	C1.pop_back();

	// C2 선거구에 포함
	C2.push_back(n + 1);
	DFS(n + 1, c1, c2 + 1);
	C2.pop_back();

}


int main()
{
	input();
	DFS(0, 0, 0);	// 몇번째 도시, c1 도시 수, c2 도시 수
	if (ans == 0x7fffffff) printf("%d\n", -1);
	else printf("%d\n", ans);
	return 0;
}

1. 조합의 경우의 수는 '링크와 스타트' 문제와 똑같이 구현해주면 된다.
=> 이때 DFS 파라미터는 Ci 구역에 포함될 구역 번호, C1 선거구에 포함되는 구역 개수, C2 선거구에 포함되는 구역 개수 로 지정해주었다.
구역번호를 파라미터로 놓으면 루프 안써도 돼서 좋다.
2. 애먹었던 것이 1.번에서 만든 선거구역에 포함된 구역들이 연결되어져 있는지 판단하는 지점이었다.
큐에 첫번째 넣는 원소는 Ci 벡터의 첫번째 요소이고, 리스트에서 Ci[0]과 연결되어져 있는 노드들을 탐색한다. 만약 방문했다면 스루하고, Ci 벡터의 원소가 아니라면(연결되어져 있기는 하지만 같은 선거구가 아니라면) 스루한다.
위의 두 조건을 모두 통과한다면, "아직 방문하지 않았고, Ci 선거구에 포함된 구역" 이므로 큐에 삽입하고 방문처리 해준다. 그리고 연결된 노드가 1개 증가했으므로 city1 변수를 +1 증가시켜준다.

선거구는 2개 이므로 위와 같은 과정을 두 번 진행해주고, 만약 cityi == Ci.size() (즉, C1[0] 과 연결되어 있는 구역의 개수가 현재 Ci 선거구에 포함된 구역의 수와 같다면) 조건을 만족하는 것이므로 true를 리턴해준다.