[그래프 / BOJ 17471 / C++] 게리맨더링

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

17471번: 게리맨더링

1) 구역을 2가지로 나누는 경우를 생각한다.
2) 1)에서 찾는 경우 중 같은 선거구끼리 인접시킬 수 있는지 확인한다.
3) 2)의 조건을 만족하는 경우 중, 두 개의 선거구 인구수의 차이가 최소가 되는 값을 찾는다.

어려웠다,,,, 생각하기 너무 힘들었던 것 같았다 dfs를 pair로 리턴해서 써먹는다면 좀 과정이 쉬워졌을 텐데 여러가지로 고생했다;;

dfs 복습 필수..!

 

이 문제의 핵심 로직은

 

1) 우선 구역들을 2가지로 나누는 경우(인접 유무와 상관없이!)를 생각해본다.

 

만약 4개의 구역이 있고, 색을 칠한다고 생각해보면, {red, red, red, blue} {red, red, blue, blue} {red,blue, red, blue} {blue,blue,red,blue}..... 등등 여러가지 경우의 수가 있다. 2^4-2 가지 경우의 수다.({blue, blue, blue, blue}와 {red, red, red, red}는 안되므로.

 

잘보면 2가지 경우의 수로 나뉘니깐, 굳이 배열을 만들 필요 없이 하나의 수로 표현할 수 있다. 즉, 0과 1을 사용하여 0001, 0010, 0100, 1000, 0011, .... 이런식으로 표현이 가능하다. 그렇다면 비트마스킹을 사용하여 경우들을 모두 찾아준다.

 

2) 1)에서 찾은 경우 중, 같은 선거구끼리 인접시킬 수 있는지 확인한다.

 

이 경우는 미리 입력받은 인접리스트를 순회하며 'connect component'를 확인하면 된다. 만약 {1 : red, 2: red, 3: blue, 4:blue} 라는 상태이고, 1-2가 인접하고, 3, 4는 인접하지 않다고 가정해보자. 그렇다면 red인 connect component는 크기가 2로 1개가 만들어지고,

blue인 connect component는 크기가 1로 2개가 만들어진다. 하지만 우리는 같은 선거구끼리 인접해야한다는 규칙을 가지고 있다.

 

즉, red인 connect component 1개의 크기와 blue인 connect component 1개의 크기의 합이 총 구역들의 개수 N과 같아야한다!!

https://die-will-coding.tistory.com/38#comment14785555

[그래프 / BOJ 1325 / C++] 효율적인 해킹

'효율적인 해킹' 문제의 로직을 이해했다면 코드를 읽는데 수월할 것이다!

 

3) 2)의 조건을 만족하는 두 개의 선거구의 인구수 차이를 구한다.

 

이 부분은 dfs를 통해 2)를 확인하면서 동시에 미리 각 선거구의 인구수들을 구해두고, 최종적으로 인구수 차이가 최소가 되는 것을 찾으면 된다. res를 INT_MAX로 설정하고, min()을 이용하면 된다. 자세한건 코드를 보자.

 

 

이 문제의 구현 방식은 요약하면 DFS + 인접리스트 + 비트마스킹 이다!! 코드를 천천히 읽으며 이해해보자.

 

dfs가 가장 중요하다!

 

#include <bits/stdc++.h>

using namespace std;

int N, n, people[11], res = INT_MAX;
vector<int> adj[11];
int vis[11], comp[11];

// dfs 공부하자,,
pair<int, int> dfs(int here, int value){ // (현위치, 지금 무슨 선거구인지.)
    vis[here] = 1; // 방문표시
    
    pair<int, int> ret = {1, people[here]}; // 현재 방문한 노드수 (=1) 백트래킹으로 올라가며 다시 return해줌, 인구수 저장.
    
    for(auto i : adj[here]){
        if(comp[i] != value) continue; // 다른 팀이면 무시
        if(vis[i]) continue; // 방문한 곳이면 무시.
        
        pair<int, int> _temp = dfs(i, value);
        ret.first += _temp.first; // 리턴해준 값을 통해 연결된 구역 개수
        ret.second += _temp.second; //리턴해준 값을 통해 총인구수 계산
    }
    
    return ret;
    
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;

    for(int i = 1 ; i <= N ; i++) cin >> people[i];

    for(int i = 1 ; i <= N ; i++){
        cin >> n;
        for(int j = 0 ; j < n ; j++){
            int tmp;
            cin >> tmp;
            adj[i].push_back(tmp);
            adj[tmp].push_back(i); // 인접 리스트 생성. 양방향임!!
        }
    }
    
    // red blue의 가지수 모두 구해보기 0과 1로 표현!! N개가 있다면, 000...1 ~ 111...0 까지
    for(int i = 1 ; i < (1 << N) - 1 ; i++){
        memset(vis, 0, sizeof(vis));
        memset(comp, 0, sizeof(comp));

        // 0에서 시작할거 한개, 1에서 시작할거 한개 고르기!
        int select1 = -1, select0 = -1;
        
        for(int j = 0 ; j < N ; j++){
            if(i & (1<<j)) {comp[j+1] = 1; select1 = j+1;} // 처음으로 켜져있는 선거구. (1번부터 시작함) & comp에는 각 선거구 정보 저장. (1번은 0, 2번은 1,,, 이런식)
            else select0 = j + 1;
        }
        
        
        pair<int, int> comp1 = dfs(select1, 1); // 1인 선거구
        pair<int, int> comp2 = dfs(select0, 0); // 0인 선거구
        
        int psum = abs(comp1.second - comp2.second); // 인구수 차이
        
        if(comp1.first + comp2.first == N) res = min(res, psum);

    }
   
    
    
    
    // 근데 adj로 2개로 나눠지는지 확인. 이는 각 adj dfs한 결과의 합이 N인지 확인하면 됨.
    // 그때의 인구수 차이를 구해서 갱신
        

    
    
    res == INT_MAX ? cout << -1 : cout << res;
    
    
}