[2024.04.09] 게리맨더링 : 그래프 이론, 완전 탐색

리뷰해볼 문제 : 백준 1741번_게리맨더링

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

17471번: 게리맨더링

 

• 푼 시간 : 4시간 이상
• 틀렸던 이유
  • 팀을 두개로 나누어야 하는데, 팀을 이룰 수 있는 조건이 "연결되어 있어야" 하는 것이라서 현재 상태에서 각 구역이 연결 가능 상태인지 확인하고 연결 가능하다면 
  • 1. 연결 하지 않고 그냥 진행
  • 2. 연결 해보고 그냥 진행
  • 이런 식으로 풀었다.
  • 그런데 새로운 구역을 연결 할 때마다 다른 구역들과의 연결 여부도 달라지니깐 새로운 구역을 연결할 때마다 이전 구역들에 대한 연결 가능 여부가 갱신되어야 한다.. 따라서 연결 가능 여부 확인 → 연결 이런 식으로 알고리즘을 구성하는 건 매우매우매우 복잡하다..!
• 풀이 
  • 1번부터 N번까지 각 구역에 대해 연결 할 지 말지에 대해 branch를 만들면서 완전 탐색을 진행한다.
  • 이때, 연결 가능 여부를 무시하고 그냥 진행해준다.
  • N개의 모든 구역에 대해 탐색이 진행되고 나서 N+1번째에 왔을 때 현재 연결 상태가 가능한 연결 상태인지 탐색하고, 연결 가능 상태이고 현재 diff가 더 작다면 minDiff 값을 갱신해준다!
  • 이때, 각 그룹의 멤버들이 연결 가능 상태인지 확인하는건 각 그룹에서 하나의 루트 노드를 정해 완전탐색을 진행했을 때, "완전 탐색으로 갈 수 있는 구역 개수 == 그룹의 개수" 라면, 해당 그룹은 가능한 상태임을 의미한다.

 

[정답 코드]

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N;//구역 수
int person[11];//각 구역의 인구수
int total = 0;//전체 인구 수
vector<int>connect[11];//각 구역과 연결된 구역목록

int ans = 1000000;//최소값

void input() {

    cin >> N;

    for (int i = 1; i <= N; i++) {
        cin >> person[i]; //인구수
        total += person[i];
    }

    for (int i = 1; i <= N; i++) {
        int n;
        cin >> n;
        for (int j = 0; j < n; j++) {
            int a;
            cin >> a;
            connect[i].push_back(a);
        }
    }
}

int curSum = 0; //A팀 인원수
int team[11] = { 0 }; //A팀이면 0, B팀이면 1


bool isGo(vector<int>team) { //team에 속하는 요소들은 모두 이어져 있는가?
    
    queue<int>q;
    q.push(team[0]);
    int cnt = 1;
    int visited[11] = { 0 };

    //team에 속하는 visited는 -1로!
    for (int i = 0; i < team.size(); i++) {
        visited[team[i]] = -1;
    }
    
    visited[team[0]] = 1;
    
    while (!q.empty()) {
        int now = q.front();
        q.pop();

        for (int i = 0; i < connect[now].size(); i++) {
            int next = connect[now][i]; //now와 연결된 구역 목록을 순차 탐색

            if (visited[next] != -1) continue; //기존에 알던 연결이거나, 우리 팀이 아니다

            //새로운 연결 발견!
            visited[next] = 1;
            cnt++;
            q.push(next);
        }
    }

    if (cnt == team.size()) return 1;
    else return 0;
}


bool isPos() { //현 구역 상태는 가능한 상태인가?

    vector<int>A;
    vector<int>B;


    for (int i = 1; i <= N; i++) {
        if (team[i] == 0) A.push_back(i);
        else B.push_back(i);
    }

    if (A.size() == 0 || B.size() == 0) return 0;

    //A팀끼리, B팀끼리 서로 연결 가능한가.
    if (!isGo(A)) {
        return 0;
    }
    if (!isGo(B)) {
        return 0;
    }
    return 1;
}

void func(int level) { //각 레벨을 A팀에 포함시킬 것인가?

    if (level == N + 1) {
        int diff = abs(total - 2 * curSum);
        //현재 구성으로 팀이루어지는지 확인
        if (diff < ans && isPos()) {
            ans = diff;
        }
        
        return;
    }

    //A팀에 포함한다.
    curSum += person[level];
    func(level + 1);
    curSum -= person[level];

    //B팀에 포함한다.
    
    team[level] = 1;
    func(level + 1);
    team[level] = 0;//원래대로
}

int main() {

    input();

    func(1);

    if (ans == 1000000) cout << -1;
    else cout << ans;

    return 0;
}