[ 백준 17471 ] 게리멘더링 (C++)

백준의 게리멘더링(17471) 문제이다.

[ 문제 바로가기 ]

[ 문제 풀이 ]

1) 주어진 구역을 2개의 선거구로 나누어서 그 2개 선거구의 인구수를 최소로 만들어야 하는 문제이다.

   본인이 가장 먼저 생각했던 것은 '조합 구현하기' 이다. 갑자기 왜 조합을 구현하는 것일까 ??

   조합을 생각해본 가장 큰 이유는 "조합으로 뽑는 놈들을 하나의 선거구, 뽑지 않은 놈들을 또 하나의 선거구"로 나누면

   될 것 같다고 생각했기 때문이다. 

   (아직 조합을 모른다면 우측의 글을 읽고오도록 하자! -->> [ 조합 알아보기(Click) ]

   우리는 주어진 N개의 구역에서 2개의 선거구를 만들어야 한다.(물론 선거구에는 최소 1개의 구역이 포함되어야 한다)

   그렇다면 N개에서 조합을 뽑으면 몇 개가 나올까?? 당연히 답을 말할 수가 없다. 왜 ? 몇 개를 뽑는지 명시를 안해줬기

   때문이다. 그렇다면 이 문제에서는 조합의 종료조건을 어떻게 설정해줘야 할까?? 보통의 문제 같은 경우 특정 갯수를

   뽑으면 return 하는식으로 구현하였지만 이 문제에서는 어떻게 해줘야할까?

   본인은 종료조건을 설정해주지 않았다. 대신, 1개 이상 뽑은 경우에는 무조건 계산을 해 주었다.

   왜?? 어차피 선거구는 최소 1개의 구역만 있어도 선거구로 취급할 수 있다.

   다시 한번 깔끔하게 정리를 해보자.

   - 조합을 왜 구현했어 ?

     - 조합을 구현하게 되면 "뽑히는 놈과, 뽑히지 않는 놈으로 구분"되기 때문에 2개의 선거구를 조합을 통해서

       뽑힌 놈들이 이루는 선거구 하나와, 뽑히지 않는 놈들이 이루는 선거구 둘로 나누기 위해서 구현했다.

   - 조합을 어떻게 구현했어 ?

     - 어떻게 해서든지 1개 이상만 뽑는다면, 2개의 선거구를 만들 수 있다는 의미이기 때문에 1개 이상만 뽑는 경우에는

       무조건 다음 단계를 진행했다.

2) 그렇다면 위의 방식대로 조합을 통해서 각각의 선거구에 포함될 구역들을 뽑았다고 가정하고 다음 단계로 넘어가보자.

   이제 바로 인구수의 차이를 구하면 될까??

   아니다. 그 전에 체크해줘야 할 것이 2가지가 있다.

   1. 선거구에 포함된 구역의 갯수가 1개 이상인지 ?

   2. 선거구에 포함된 구역들 끼리 모두 연결되어 있는지 ?

   를 체크해주어야 한다.

   2번은 그렇다쳐도 1번조건 같은 경우에는 애초에 조합을 구현할 때 1개 이상 뽑은 경우에만 지금 이 단계로 넘어왔기

   때문에 고려를 해줘야할까 ??

   해줘야 한다. 1개 이상만 뽑은 경우에는 "존재하는 모든 구역을 다 뽑은 경우" 도 포함되어 지게 된다.

   예를 들어서 구역이 1~6번까지 총 6개의 구역이 있다고 가정했을 때, 저 "1개 이상 뽑은 경우" 에는

   { 1, 2, 3, 4, 5, 6 } 이렇게 6개의 구역을 모두 뽑은 경우도 포함된다는 것이다.

   저렇게 되면? 뽑히지 않은 구역의 갯수가 0개, 즉 2번째 선거구가 가질 수 있는 구역의 갯수가 0개가 되어버린다.

   이는, "선거구는 구역을 적어도 하나 포함해야된다" 라는 문제의 조건에 어긋나게 된다. 따라서, 1번 조건도 반드시

   체크를 해줘야 한다.

  

   본인은 위의 2가지 조건을 체크해주기 전에, 관리를 편하게 하기 위해서 벡터에 각 선거구에 포함된 구역들을 넣어주었다.

   1번 조건 같은 경우에는, 각각의 벡터 사이즈가 0 이상인지만 체크해주면 판단이 가능하다.

   2번은 조건은 어떻게 판단해 주어야 할까 ??

   일단, 다시 가장 처음으로 넘어가서 입력받는 부분을 생각해보자. 우리는 각 구역들 간의 연결 관계가 입력으로 주어진다.

   이 때, 본인은 2차원 배열(본문 : bool Connect[][]) 을 통해서 미리 체크를 해두었다.

   즉, Connect[a][b] = true 는 "a구역과 b구역은 연결되어 있습니다." 를 의미한다.

   다시 돌아와서 2번 조건을 생각해보자. 본인은 2번 조건을 너비우선탐색인 BFS를 이용해서 구현해 보았다.

   BFS에서의 탐색 조건은 다음과 같다.

   1. 현재 구역과 탐색하려는 구역이 연결되어 있는 구역인지

   2. 탐색하려는 구역이 현재 선거구에 맞는 놈인지

   3. 아직 방문하지 않은 구역인지

   위 3개의 조건을 하나하나 알아보자.

   1번조건. 일단 선거구에 존재하는 모든 구역들 끼리는 연결되어 있어야 하므로 체크해 주어야 한다.

   2번조건. 탐색하려는 구역이 현재 선거구에 맞는 놈인지 체크해주어야 한다는 것이다.

   예를 들어서, 구역 1과 구역 2가 연결되어 있지만, 조합을 통해서 1은 뽑혔고 2는 뽑히지 않은 상태라고 생각해보자.

   그렇다면 1번 구역에서 BFS탐색시 2번 구역을 탐색해야 할까? 아니다 ! 연결되어 있을 뿐, 같은 선거구가 아니기 때문에

   탐색을 해주면 안된다. 따라서 2번 조건도 체크를 해줘야한다.

   3번 조건은 BFS에서 필수 !

  

   위와 같은 방식으로 선거구들이 갖는 조건들 까지 모두 체크해서 만족할 경우, 이제 인구수를 체크해주면 된다.

 

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
 
#define endl "\n"
#define MAX 10 + 1
using namespace std;
 
int N, Answer = 987654321;
int Person[MAX];        // 인구수를 저장하기 위한 배열
bool Connect[MAX][MAX];    // 구역들 간의 연결관계를 저장하기 위한 배열
bool Select[MAX];        // 조합 구현 시, 뽑은 데이터에 대한 체크를 저장하기 위한 배열
bool Visit[MAX];        // BFS탐색 시, 방문 탐색을 체크하기 위한 배열
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        int x; cin >> x;
        Person[i] = x;
    }
    for (int i = 1; i <= N; i++)
    {
        int Cnt; cin >> Cnt;
        for (int j = 0; j < Cnt; j++)
        {
            int a; cin >> a;
            Connect[i][a] = true;
            Connect[a][i] = true;
        }
    }
}
 
bool Check_Connection(vector<int> V, bool T)
{
    /* 2번 조건 : 선거구에 포함된 구역들끼리 모두 연결되어 있는지 ?
       를 체크해주기 위한 BFS 함수.
    */
 
    memset(Visit, false, sizeof(Visit));
    queue<int> Q;
    Q.push(V[0]);        
    Visit[V[0]] = true;
    int Cnt = 1;
 
    while (Q.empty() == 0)
    {
        int x = Q.front();
        Q.pop();
 
        for (int i = 1; i <= N; i++)
        {
            /* BFS 탐색 조건 3개
               조건 1 : 현재 구역과 탐색하려는 구역이 연결되어 있는지 ?
               조건 2 : 탐색하려는 구역이 선거구에 맞는 놈인지 ?
               조건 3 : 아직 방문하지 않은 구역인지 ? 
            */
            if (Connect[x][i] == true && Select[i] == T && Visit[i] == false)
            {
                Visit[i] = true;
                Cnt++;        // 갯수를 계속해서 Count
                Q.push(i);
            }
        }
    }
 
    /* 2번 조건에 위배 되지 않는다 = BFS에서 Count한 값과 Vector의 Size가 같다. */
    if (V.size() == Cnt) return true;
    return false;
}
 
bool Check()
{
    /* 선거구가 가질 수 있는 조건들에 대해서 Check 해주는 함수.
       조건 1 : 선거구에 포함된 구역의 갯수가 1개 이상인지 ?
       조건 2 : 선거구에 포함된 구역들 끼리 모두 연결되어 있는지 ? 
    */
 
    vector<int> A, B;
    for (int i = 1; i <= N; i++)
    {
        if (Select[i] == true) A.push_back(i); // 1선거구 = A Vector
        else B.push_back(i);                   // 2선거구 = B Vector
    }
 
    /* 1번 조건 Check */
    if (A.size() == 0 || B.size() == 0) return false;
 
    /* 2번 조건 Check */
    bool AState = Check_Connection(A, true);
    if (AState == false) return false;
 
    bool BState = Check_Connection(B, false);
    if (BState == false) return false;
 
    return true;
}
 
void Calculate()
{
    /* 인구수 차이를 구하기 위한 함수 */
    int A_Num, B_Num, Diff;
    A_Num = B_Num = 0;
 
    for (int i = 1; i <= N; i++)
    {
        if (Select[i] == true) A_Num = A_Num + Person[i];
        else B_Num = B_Num + Person[i];
    }
    Diff = abs(A_Num - B_Num);
    if (Answer > Diff) Answer = Diff;
}
 
void DFS(int Idx, int Cnt)
{
    /* 조합 구현을 위한 DFS 함수. */
    if (Cnt >= 1)
    {
        /* 최소 1개 이상의 원소만 뽑으면 모두 계산해줄 것이므로 조건문 : Cnt >= 1 */
        if (Check() == true)
        {
            Calculate();
        }
        // return이 없으니 조심하자 ! 
    }
 
    for (int i = Idx; i <= N; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        DFS(i, Cnt + 1);
        Select[i] = false;
    }
}
 
void Solution()
{
    DFS(1, 0);     
 
    if (Answer == 987654321) cout << -1 << endl;
    else cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}