[백준] 17471번 : 게리맨더링

문제

 

---

풀이

 

할게 많아보이는데 그렇게 많진 않다.

 

1. 두 선거구로 나눈다.

2. 두 선거구의 인구 차이를 구한다.

3. 두 선거구를 올바르게 나눴다면 인구 차이의 최솟값을 갱신한다.

 

2번과 3번의 순서가 바뀌어야 하지 않나?라고 생각할 수도 있다.

근데 인구 차이를 먼저 구하고 그 값이 현재의 최솟값보다 크거나 같다면 3번을 실행하지 않을 것이다.

그럼 불필요한 연산을 하지 않으니 시간이 좀 줄어들 것이다.

 

두 선거구를 나누는 조합 연산은 비트마스킹으로 했다.

---

소스코드

 

#include <iostream>
#include <vector>

using namespace std;

vector<bool> split, visited;
vector<int> population;
vector<vector<int>> graph;

int calcDiff() { //두 선거구의 인구 차이
    int blue = 0, red = 0;
    for (int i = 1; i < split.size(); i++) {
        if (split[i])
            blue += population[i];
        else
            red += population[i];
    }
    return abs(blue - red);
}

void dfs(int cur) {
    visited[cur] = true; //방문 처리
    for (int i = 0; i < graph[cur].size(); i++) {
        int node = graph[cur][i];
        if (split[node] == split[cur] && !visited[node]) //같은 선거구이면서 방문하지 않은 곳일 때
            dfs(node);
    }
}

int main() {
    int N, num, input, result = 10000;

    cin >> N;
    graph.assign(N + 1, vector<int>(0));
    population.assign(N + 1, 0);
    split.assign(N + 1, false);
    for (int i = 1; i <= N; i++)
        cin >> population[i];
    for (int i = 1; i <= N; i++) {
        cin >> num;
        while (num--) {
            cin >> input;
            graph[i].push_back(input);
        }
    }
    for (int i = 1; i < (1 << N) - 1; i++) { //비트마스크 조합
        for (int j = 0; j < N; j++) //각 선거구로 나눠줌
            split[j + 1] = (i & (1 << j)) != 0;
        int diff = calcDiff(); //인구 수 차이
        if (diff >= result) //최솟값보다 크다면 탐색할 필요 없음
            continue;

        visited.assign(N + 1, false);
        int cnt = 0; //dfs를 돈 횟수
        for (int j = 1; j <= N && cnt < 3; j++) { //각 선거구가 연결됐다면 dfs가 2번만 실행돼야 함
            if (!visited[j]) {
                cnt++;
                dfs(j);
            }
        }
        if (cnt == 2) //각 선거구가 연결됐다면 갱신
            result = diff;
    }
    cout << ((result == 10000) ? -1 : result); //출력
}

전체 소스코드다.

 

vector<bool> split, visited;
vector<int> population;
vector<vector<int>> graph;

split으로 각 지역이 어떤 선거구에 들어갔는지 표시하는데 쓰고, visited는 dfs에 쓸 것이다.

population에 각 지역의 인구수를 저장하고, 지역의 연결관계는 graph에 저장한다.

 

    cin >> N;
    graph.assign(N + 1, vector<int>(0));
    population.assign(N + 1, 0);
    split.assign(N + 1, false);
    for (int i = 1; i <= N; i++)
        cin >> population[i];
    for (int i = 1; i <= N; i++) {
        cin >> num;
        while (num--) {
            cin >> input;
            graph[i].push_back(input);
        }
    }

입력을 받는 부분이고...

 

    for (int i = 1; i < (1 << N) - 1; i++) { //비트마스크 조합
        for (int j = 0; j < N; j++) //각 선거구로 나눠줌
            split[j + 1] = (i & (1 << j)) != 0;
        int diff = calcDiff(); //인구 수 차이
        if (diff >= result) //최솟값보다 크다면 탐색할 필요 없음
            continue;

        visited.assign(N + 1, false);
        int cnt = 0; //dfs를 돈 횟수
        for (int j = 1; j <= N && cnt < 3; j++) { //각 선거구가 연결됐다면 dfs가 2번만 실행돼야 함
            if (!visited[j]) {
                cnt++;
                dfs(j);
            }
        }
        if (cnt == 2) //각 선거구가 연결됐다면 갱신
            result = diff;
    }

비트마스크로 구한 각 조합에 대해 연산을 한다.

모든 지역이 한 구역에 속한 경우는 제외해야 하기 때문에, 0과 111...1111을 제외했다.

 

        for (int j = 0; j < N; j++) //각 선거구로 나눠줌
            split[j + 1] = (i & (1 << j)) != 0;

대충 101100이면 1, 2, 5번 지역은 빨간색이고, 3, 4, 6번 지역은 파란색으로 표시하는 것이다.

 

        int diff = calcDiff(); //인구 수 차이
        if (diff >= result) //최솟값보다 크다면 탐색할 필요 없음
            continue;

이 조합에 대해 인구 수의 차이를 구하고, 이게 현재의 최솟값이 result면 더이상 살펴보지 않는다.

 

int calcDiff() { //두 선거구의 인구 차이
    int blue = 0, red = 0;
    for (int i = 1; i < split.size(); i++) {
        if (split[i])
            blue += population[i];
        else
            red += population[i];
    }
    return abs(blue - red);
}

인구 수의 차이는 그냥 이렇게 구한다.

 

        visited.assign(N + 1, false);
        int cnt = 0; //dfs를 돈 횟수
        for (int j = 1; j <= N && cnt < 3; j++) { //각 선거구가 연결됐다면 dfs가 2번만 실행돼야 함
            if (!visited[j]) {
                cnt++;
                dfs(j);
            }
        }

이제 dfs로 선거구를 잘 나눴는지 확인한다.

제대로 나눴다면 dfs는 2번만 실행되어야 한다. (파랑 1번, 빨강 1번)

 

void dfs(int cur) {
    visited[cur] = true; //방문 처리
    for (int i = 0; i < graph[cur].size(); i++) {
        int node = graph[cur][i];
        if (split[node] == split[cur] && !visited[node]) //같은 선거구이면서 방문하지 않은 곳일 때
            dfs(node);
    }
}

dfs는 간단하게 구현했다.

 

        if (cnt == 2) //각 선거구가 연결됐다면 갱신
            result = diff;

그래서 dfs가 2번만 실행된 것까지 확인했다면 result를 갱신한다.

 

    cout << ((result == 10000) ? -1 : result); //출력

출력하면 끝