[C++] 백준 17471 - 게리맨더링

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

17471번: 게리맨더링

<풀이>

1. 구역의 정보를 입력받는다.

2. 조건에 맞게 구역들을 두 개의 선거구에 포함시키고, 두 선거구간 인구 차이의 최솟값을 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 모든 경우를 다 해보아야합니다. 따라서, 저는 브루트포스를 선택하였습니다. 하지만, 여기서 한번 멈칫했습니다. 구역들은 한 선거구가 되려면 모두 연결되어있어야합니다. 그러면 이 조건을 (1)구역들을 뽑을 때 검사해야하나 (2)구역을 다 나눠놓고 검사해도되나 망설여집니다. 저는 시간복잡도를 따져보았습니다. 구역은 10개 이하로 주어지므로, 연산횟수는 1024회 입니다. 따라서, 저는 (2)를 선택했습니다.

 

2. 구역들이 모두 연결되어있는지 확인하기

=> 구역들을 두 개로 나누었다면, 같은 선거구의 구역들이 모두 연결되어있는지 확인해야 합니다. 저는 BFS를 이용해서 조건을 확인했습니다.

 

3. 구현 전 총정리

=> 아래는 구현 전 정리한 생각입니다.

(1) 브루트포스 중 DFS를 선택하고, 재귀함수로 구현한다. 구역들을 두 선거구로 나누는 모든 경우를 해본다.

(2) 두 선거구로 나누었으면, ①두 선거구에 구역들이 하나라도 포함되어있는지 확인하고, ②같은 선거구에 있는 구역들이 모두 연결되어있는지 확인합니다. 

(3) 두 선거구간 인구차이의 최소를 return한다.

자세한 구현은 아래 코드를 참조해주세요.

 

#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#define INF 987654321
 
using namespace std;
 
int N;
int people[11];
bool edge[11][11];
vector<int> a, b;
int answer;
 
bool isLinked(vector<int> sector) {
    queue<int> q;
    bool visited[11];
    memset(visited, false, sizeof(visited));
 
    int start = sector.front();
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = 0; i < sector.size(); i++) {
            int nxt = sector[i];
            if (!visited[nxt] && edge[cur][nxt]) {
                q.push(nxt);
                visited[nxt] = true;
            }
        }
    }
 
    for (int i = 0; i < sector.size(); i++) {
        int node = sector[i];
        if (!visited[node]) return false;
    }
    return true;
}
 
int divideSector(int idx, int sumA, int sumB) {
    if (idx > N) {
        if (!sumA || !sumB) return INF;
        else {
            if (isLinked(a) && isLinked(b)) return abs(sumA - sumB);
            else return INF;
        }
    }
 
    int ret = INF;
    //a구역에 넣는 경우
    a.push_back(idx);
    ret = min(ret, divideSector(idx + 1, sumA + people[idx], sumB));
    a.pop_back();
    //b구역에 넣는 경우
    b.push_back(idx);
    ret = min(ret, divideSector(idx + 1, sumA, sumB + people[idx]));
    b.pop_back();
    return ret;
}
 
void solution() {
    answer = divideSector(1, 0, 0);
    answer = (answer == INF) ? -1 : answer;
}
 
int main() {
    //초기화
    N = 0;
    memset(people, 0, sizeof(people));
    memset(edge, false, sizeof(edge));
    answer = 0;
 
    //입력
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> people[i];
    }
    for (int i = 1; i <= N; i++) {
        int cnt = 0;
        cin >> cnt;
        for (int j = 0; j < cnt; j++) {
            int node = 0;
            cin >> node;
            edge[i][node] = true;
        }
    }
 
    //해법
    solution();
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}

 

DFS와 BFS에 대해 알아볼 수 있는 문제였습니다.