백준 17471 게리 맨더링

문제

문제 링크 : (https://www.acmicpc.net/problem/17471)

문제분석

쉽게보고 접근했는데 생각보다 시간을 오래 잡아먹었다.
(한시간은 훌쩍 넘긴듯하다..)

문제속의 문제는 크게 두가지로 나뉜다.

1. 백트래킹을 이용한 순열 알고리즘으로 n개의 구역에서 red와 blue 구역을 나누는 작업

2.선택한 구역이 각각 서로 연결되어 있는지 확인

1번 작업은 백트래킹을 이용하지 않고 stl의 next_permutation 을 사용하면 조금 더 쉽게 해결할 수 있지만 연습하는겸 해서 직접 골라내봤다.

2번 작업도 처음에 반복문으로 돌려가며 탐색하다가 보기에 너무 지저분해서 find함수를 적용해 다시 작성했다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define INF 2147483647
int n;
int arr[11];
bool vi[11];
int mindiff = INF;
vector<int> link[11];
vector<int> reds,blue;
void check2(int start, vector<int> &v) {
	int cnt = 0;
	for (int i = 0; i < link[start].size(); i++) {
		auto it = find(v.begin(), v.end(), link[start][i]);
		if (it == v.end()) continue;
		if (vi[*it]) continue;
		vi[*it] = true;
		check2(*it, v);
	}
}

bool check(vector<int> &v) {
	fill(vi, vi + n + 1, false);
	vi[v[0]] = true;
	check2(v[0], v);
	for (int i = 0; i < v.size(); i++) {
		if (!vi[v[i]]) return false;
	}
	return true;
}


void permutation(int sel, int idx, int cnt) {
	if (idx==n+1) {
		if (reds.size() >= 1 && blue.size()>=1) {
			if (check(reds) && check(blue)) {		
				int sum1 = 0, sum2 = 0;
				for (int i = 0; i < reds.size(); i++) sum1 += arr[reds[i]];
				for (int i = 0; i < blue.size(); i++) sum2 += arr[blue[i]];
				mindiff = min(mindiff, abs(sum1 - sum2));
			}
		}
		return;
	}
	
	if (cnt != sel) {
		reds.push_back(idx);
		permutation(sel, idx + 1, cnt + 1);
		reds.pop_back();
	}
	blue.push_back(idx);
	permutation(sel, idx + 1, cnt);
	blue.pop_back();
}

int main(){
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> arr[i];
	for (int i = 1; i <= n; i++) {
		int a; cin >> a;
		for (int j = 0; j < a; j++) {
			int b; cin >> b;
			link[i].push_back(b);
		}
	}
	for (int i = 1; i < n; i++) {
		permutation(i, 1, 0);
	}
	if (mindiff == INF) cout << -1;
	else cout << mindiff;
}

추가

자고나서 맑은 정신으로 짰으면 더 빨리 풀었을것 같다.
나중에 코테 보게되면 전날은 푹자자..