백준 17471번 게리맨더링 C++

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

 

1. 한 구역에서 구역으로 갈 수 있는지 확인할 수 있는 2차원 배열을 만든다.

2. 백트래킹으로 구역을 나누는 경우를 모두 찾는다.

3. 두개의 선거구가 있을텐데, 선거구의 구역들이 다 이어져있는지 확인한다.

4. 구역들이 이어져있지만 다른 선거구가 끼어있는 경우를 걸러준다.

5. 두 선거구의 인구 차를 구하면서 최솟값을 찾는다.

 

골드4문제인데 골드4보단 어려웠던 것 같다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

#define OUT

using namespace std;
using int64 = long long;

int n;
int sum = 0;
int ans = 987654321;
vector<int> population;
vector<bool> visited;
vector<vector<bool>> CanGo;
vector<vector<int>> graph;

void RefreshVisited() {
    for (int i = 1; i <= n; i++)
        visited[i] = false;
}

void Dfs(int city, int start, vector<vector<bool>>& canGo) {
    visited[city] = true;
    canGo[start][city] = true;
    for (auto next : graph[city]) {
        if (visited[next]) continue;
        Dfs(next, start, canGo);
    }
}

vector<bool> visited_BT;
set<int> s;
set<int> otherSet;

void BT(int idx) {

    if (s.size() >= 1 && s.size() < n) {
        bool connected = true;
        int begin = *s.begin();
        for (auto a : s) {
            if (!CanGo[begin][a]) connected = false;
        }
        begin = *otherSet.begin();
        for (auto a : otherSet) {
            if (!CanGo[begin][a]) connected = false;
        }
        if (connected) {
            
            vector<vector<bool>> _canGo(n + 1, vector<bool>(n + 1, false));
            RefreshVisited();
            for (auto a : s) {
                visited[a] = true;
            }
            Dfs(begin, begin, _canGo);
            for (auto a : otherSet) {
                if (!_canGo[begin][a]) connected = false;
            }

            _canGo = vector<vector<bool>>(n + 1, vector<bool>(n + 1, false));
            RefreshVisited();
            for (auto a : otherSet) {
                visited[a] = true;
            }
            int begin = *s.begin();
            Dfs(begin, begin, _canGo);
            for (auto a : s) {
                if (!_canGo[begin][a]) connected = false;
            }

            if (connected) {
                int currSum = 0;
                for (auto a : s) {
                    currSum += population[a];
                }
                int otherSum = sum - currSum;
                int gap = abs(currSum - otherSum);
                ans = min(ans, gap);
            }
        }
    }

    for (int i = idx; i <= n; i++) {
        if (visited_BT[i]) continue;
        visited_BT[i] = true;
        s.insert(i);
        otherSet.erase(i);
        BT(i + 1);
        visited_BT[i] = false;
        s.erase(i);
        otherSet.insert(i);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    population = vector<int>(n + 1);
    visited = vector<bool>(n + 1, false);
    visited_BT = vector<bool>(n + 1, false);
    CanGo = vector<vector<bool>>(n + 1, vector<bool>(n + 1, false));
    graph = vector<vector<int>>(n + 1, vector<int>());
    for (int i = 1; i <= n; i++) {
        cin >> population[i];
        sum += population[i];
        otherSet.insert(i);
    }
    for (int i = 1; i <= n; i++) {
        int cnt;
        cin >> cnt;
        for (int j = 0; j < cnt; j++) {
            int city;
            cin >> city;
            graph[i].push_back(city);
        }
    }
    for (int i = 1; i <= n; i++) {
        RefreshVisited();
        Dfs(i, i, CanGo);
    }
    BT(1);
    if (ans == 987654321) cout << -1;
    else cout << ans;
}