17471-게리맨더링

www.acmicpc.net/problem/17471

17471번: 게리맨더링

그래프, 조합, DFS에 대한 개념이 필요한 문제였습니다. 알고리즘 문제를 풀다보면 어떤 문제들은 풀고나면 많은 배움을 얻었다고 느껴지는 문제들이 있습니다. 해당 문제가 이러한 문제였습니다. 

 

결국 스스로의 힘으로 문제를 풀지는 못하고 솔루션을 보고서야 이해하고 풀 수 있었습니다. 특히, 조합을 생성하는데 있어 막힘이 있었습니다. N과 M 문제들을 다시 한 번 쭈욱 풀어봐야겠습니다.

 

알고리즘을 간략하게 나타내면 다음과 같습니다.

 

1. 구역간의 연결관계를 그래프로 표현하고 이를 저장한다.

아래 코드 상에서 2차원 벡터(vector<vector<int>> g)의 데이터 삽입 부분 참고

 

2. 주어진 구역들을 두 개의 선거구로 나눈다.

두 개의 선거구로 나누기 위해 N 개의 지역을 n개, N-n개로 나누어야 한다.(여기서, n의 범위는 [1, N-1]이다.) 즉, 조합에 관한 문제이다.  next_permutation 함수를 사용하여 N개의 지역을 두 개의 선거구로 나누는 경우를 모두 탐색한다. 그리고 실제로 나누어지는 경우(문제 규칙 참조)만을 제외하고 나머지 경우는 버린다. 

 

3. N개의 지역을 두 개의 선거구로 나누는 경우에 대해 구역간의 인구차를 구하고 최소 인구차를 저장한다.

 

4. 최소 인구차를 출력한다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <climits>
using namespace std;

int N;
vector<vector<int>> g;
vector<int> num;
vector<bool> visited;

int visit_neighbor_city(int idx_city, vector<int>& perm, int type)
{
    int cnt = 1;

    visited[idx_city] = true;

    for(int idx_neighbor_city:g[idx_city])
    {
        if(visited[idx_neighbor_city] == false)
        {
            visited[idx_neighbor_city] = true;

            if(perm[idx_neighbor_city - 1] == type)
            {
                cnt += visit_neighbor_city(idx_neighbor_city, perm, type);         
            }
        }
    }

    return cnt;
}

int main()
{
    //freopen("17471.txt", "r", stdin);
    
    cin >> N;
    num.resize(N + 1);
    g.resize(N + 1);
    visited.resize(N + 1);

    for(int i = 1; i <= N; i++) 
    {
        cin >> num[i];
    }

    for(int from = 1; from <= N; from++)
    {
        int n;
        cin >> n;

        g[from].resize(n);
        for(int i = 0; i < n; i++) 
        {
            cin >> g[from][i];
        }
    }

    int answer = INT_MAX;

    for(int n = 1; n <= N-1; n++)
    {
        vector<int> perm(n, 0);
		for (int i = n + 1; i <= N; i++)
        {
			perm.push_back(1);
        }

        int nA = n; //A 도시 수
        int nB = N-n; //B 도시 수

        do
        {
            int idx_city_a = -1;
            int idx_city_b = -1;

            for(int i = 0; i < perm.size(); i++)
            {
                if(idx_city_a != -1 and idx_city_b != -1) break;
    
                if(idx_city_a == -1 and perm[i] == 0) idx_city_a = i;
                else if(idx_city_b == -1 and perm[i] == 1) idx_city_b = i;
            }

            fill (visited.begin(), visited.end(), false);
            int connected_nA = visit_neighbor_city(idx_city_a + 1 , perm, 0);//perm 은 0부터 indexing, 나머지는 1부터 indexing

            fill (visited.begin(), visited.end(), false);
            int connected_nB = visit_neighbor_city(idx_city_b + 1 , perm, 1);

            if(connected_nA == nA and connected_nB == nB)
            {
                int sumA = 0;
                int sumB = 0;
                for(int i = 0; i < perm.size(); i++)
                {
                    if(perm[i] == 0) sumA += num[i+1];
                    else if(perm[i] == 1) sumB += num[i+1];
                }

                answer = min(answer, abs(sumA-sumB));
            }

        } while (next_permutation(perm.begin(), perm.end()));//작은 수 부터 큰 수를 반환
    }

    if(answer == INT_MAX) cout << -1;
    else cout << answer;

    return 0;
}