[Algorithm] BOJ 17471 게리맨더링

틀린 부분 또는 더 효율적인 접근법에 대해 피드백 주시면 감사하겠습니다!

---

17471 게리맨더링

---

문제

백준시의 시장 최백준은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 최백준은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 백준시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.

백준시는 N개의 구역으로 나누어져 있고, 구역은 1번부터 N번까지 번호가 매겨져 있다. 구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.

아래 그림은 6개의 구역이 있는 것이고, 인접한 구역은 선으로 연결되어 있다.

공평하게 선거구를 나누기 위해 두 선거구에 포함된 인구의 차이를 최소로 하려고 한다. 백준시의 정보가 주어졌을 때, 인구 차이의 최솟값을 구해보자.

입력

첫째 줄에 구역의 개수 N이 주어진다. 둘째 줄에 구역의 인구가 1번 구역부터 N번 구역까지 순서대로 주어진다. 인구는 공백으로 구분되어져 있다.

셋째 줄부터 N개의 줄에 각 구역과 인접한 구역의 정보가 주어진다. 각 정보의 첫 번째 정수는 그 구역과 인접한 구역의 수이고, 이후 인접한 구역의 번호가 주어진다. 모든 값은 정수로 구분되어져 있다.

구역 A가 구역 B와 인접하면 구역 B도 구역 A와 인접하다. 인접한 구역이 없을 수도 있다.

• 2 ≤ N ≤ 10
• 1 ≤ 구역의 인구 수 ≤ 100

출력

첫째 줄에 백준시를 두 선거구로 나누었을 때, 두 선거구의 인구 차이의 최솟값을 출력한다. 두 선거구로 나눌 수 없는 경우에는 -1을 출력한다.

예제

---

풀이

---

생각

• 바로 백트랙킹으로 풀면 되겠다고 생각했다.
  • 모든 선거구의 경우를 찾아, 인구차이 계산하면 되겠구나 !
  • 하나의 선거구만 찾으면, 나머지 선거구가 알아서 정해지겠구나 !
  • 고로, check만 활용해 하나의 선거구만 찾아보자 ! (vector 사용X)
  • 라는 흐름으로 풀게 되었다.
• 대략적으로 계산은 되지만, 예제에서 틀린 경우가 발생했다.
  • 왜지? 생각하던 중... 하나의 선거구만 선택하는 걸 계속 의식해서 그런지, 하나의 선거구만 연결되어 있는가 체크하고 있었다.
  • 그럼 '다른 선거구도 연결되어 있는지 체크해야지!'라고 생각했으나, 그럼 check의 반대의 경우를 계산해서 다시 또 이걸 연결되어 있는가 찾아가는 과정이 seamless 하지 않았다.
• 그래서 vector를 활용. v1, v2를 2개의 선거구로 두고, 모든 경우의 수를 계산했다.
  • 일반 백트랙킹처럼 dfs로 들어왔을 때 0부터 시작할 필요가 없었다.
  • 예를 들어, 0하고 3을 선택했다하자. 모든 for문을 0부터 시작하게 될 경우, 이후에 3하고 0을 선택하게 될 텐데, 여기선 순서가 상관없는 문제였기에 이럴 필요가 없었다.
  • 고로, 이전 선택의 값 이상인 값만 순회하며 모든 경우의 수를 계산하면 되게 구현했다.

방법

• 이 문제의 경우, 이전 게시글보다 짧게 설명하겠다.
  • 주석에 자세히 적어놓았기 때문에...
• 문제의 핵심은 dfs를 이용한 백트랙킹과 bfs를 이용한 연결확인
• 백트랙킹으로 모든 경우의 수를 계산한다.
  • 일반적인 백트랙킹처럼 어느 수(n)이 됬을 때 특정한 연산으로 들어가는 것이 아닌, for문이 끝났을 때 특정한 연산으로 들어가야 한다.
  • 수를 채우는게 문제가 아닌 선택을 어떻게 하느냐이기 때문에.
• 경우의 수를 구하는 과정에서 v1 vector 완성
  • 경우의 수를 다 구하면, check를 이용해 반대 선거구인 v2 vector 완성
• 이제 v1, v2가 각 선거구끼리 연결되어있는가를 bfs로 확인
  • bfs과정에서 visited로 각 지역에서 인접한 구역을 체킹
  • 이렇게 되면, 연결되지 않은 선거구인 경우 visited가 false로 되서 확인과정에서 연결되지 않은 것을 확인할 수 있다.
• 연결되어있음을 확인 했으면, 선거구의 인구차이를 계산하고, 기존 최소 인구차이와 비교해서 더 작을 시 업데이트.

유의

• 연결되어있는 지역 input 받을 때, 1부터 시작하는 값으로 받기 때문에 조정이 필요하다. 받을 때 1을 빼서 받거나, 이후 접근할 때 1을 빼서 접근하거나, 아니면 그냥 공간을 더 크게 만들어놓거나 하는 식으로 해야한다.
• 이 문제도 내가 너무 섣불리 자료구조, 변수네이밍을 했다고 생각했다.
  • 이후에 가니 numNear은 뭐고, near은 뭐지 헷갈렸다.
  • 명확히 네이밍하고, 이 값이 무엇을 의미하는지 주석으로 적어놓고 하는 것도 중요하다고 생각.
• 경우의 수가 매우 적다. N이 커봤자 10이므로...
  • 그 뜻은, 0.5초가 시간제한이더라도 모든 경우의 수 다 돌아도 무리없다는 것 같다. (내 생각...)
  • 선거구 vector로 나누고, 이거 순회하면 오래걸리지않나 막 이런생각하면서 풀었다.

---

코드

---

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
#define bb ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define SIZE 11
using namespace std;
struct district {
    int numPer, numNear;
};
int n, near[SIZE][SIZE], allPer;
int res = 10'000;    // 인구차이는 100*10을 넘을 수 없다.
district d[SIZE];
bool check[SIZE], visit[SIZE];
vector<int> v1, v2; // 2개의 선거구


// 선거구가 연결되어 있는가? True/False
bool connected() {
    int present;

    // BFS를 활용하자
    memset(visit, 0, sizeof(visit)); // visit 초기화
    queue<int> q; 

    // 첫 번째 선거구 - BFS 레퍼토리 시작
    q.push(v1[0]);
    visit[v1[0]] = true;
    while (!q.empty()) {
        present = q.front();
        q.pop();
        for (int j = 0; j < d[present].numNear; ++j) {
            int n = near[present][j];    // 인접해 있는 지역 넣기
            if (visit[n]) continue;        // 이미 들렸던 곳인 경우, 패스
            if (!check[n]) continue;    // 다른 선거구일 경우, 패스
            q.push(n);
            visit[n] = true;
        }
    }

    // 첫 번째 선거구 지역을 다 돌았는가? --> 다 연결되어 있는가 확인
    for (int i = 0; i < v1.size(); ++i) {
        if (!visit[v1[i]]) return false;
    }


    memset(visit, 0, sizeof(visit)); // visit 초기화

    // 두 번쨰 선거구 - BFS 레퍼토리 시작
    q.push(v2[0]);
    visit[v2[0]] = true;
    while (!q.empty()) {
        present = q.front();
        q.pop();
        for (int j = 0; j < d[present].numNear; ++j) {
            int n = near[present][j];    // 인접해 있는 지역 넣기
            if (visit[n]) continue;        // 이미 들렸던 곳인 경우, 패스
            if (check[n]) continue;        // 다른 선거구일 경우, 패스
            q.push(n);
            visit[n] = true;
        }
    }

    // 두 번째 선거구 지역을 다 돌았는가? --> 다 연결되어 있는가 확인
    for (int i = 0; i < v2.size(); ++i) {
        if (!visit[v2[i]]) return false;
    }

    return true;
}

// 백트랙킹 --> 전체경우 확인
// 선거구 확인하고, 가능하면 인구차이 최소 값 계산 및 비교
void solution(int cnt, int last) {
    // n인 경우, 한 선거구로 다 몰린 경우이므로 패스
    if (cnt == n) return; 

    /*
    백트랙킹.
    - 1, 5 선택하는 것과 5, 1 선택하는 것은 같은 경우 이므로 0부터 할 필요없다.
    - 전 선택의 마지막 값을 받아서 그 값 이상인 경우만 순회하면 된다.

    - 선택하는 과정은 한 번만 하면 된다. 선택하지 않은 선거구를 또 다른 선거구로 지정하면 되므로.
    - 선택한 선거구 v1, 선택하지 않은 선거구 v2
    */
    for (int i = last; i < n; ++i) {
        if (check[i]) continue;
        v1.push_back(i);
        check[i] = true;
        solution(cnt + 1, i+1);
        v1.pop_back();
        check[i] = false;
    }

    // 0인 경우도 한 선거구로 다 몰린 경우이므로 패스
    if (cnt == 0) return;

    int aPer = 0;    // 선택한 선거구의 인구 수
    v2.clear();
    for (int i = 0; i < n; ++i) {
        if (!check[i])
            v2.push_back(i);    // 선택하지 않은 선거구 -> v2
        else
            aPer += d[i].numPer;
    }

    // v1, v2 다 각 선거구 연결되어있는 경우,
    if (connected())
        res = min(abs(aPer - (allPer - aPer)), res); // 인구차이 최소값 계산 및 비교

}


int main() {
    // input
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> d[i].numPer;
        allPer += d[i].numPer;    // 전체 인구수 계산
    }
    for (int i = 0; i < n; ++i) {
        cin >> d[i].numNear;
        for (int j = 0; j < d[i].numNear; ++j) {
            cin >> near[i][j];
            --near[i][j]; // 배열 인덱스 접근하는 것이므로 1을 빼줌
        }
    }

    solution(0, 0);    

    if (res > 9000)
        cout << -1 << '\n';
    else
        cout << res << '\n';
    return 0;
}

---

느낀점

• 백트랙킹과 BFS순회를 함께 사용해서 좀 참신했다.
• 그리고 기존 백트랙킹의 경우, count가 특정 수가 되서 멈출 때 뭔가 특정연산으로 넘어간다던가 했는데 여긴 그 반대여서 풀면서 재밌었다. 문제만든 사람 진짜 대단하다고 생각.
• 간단히 문제를 쪼개서 풀면 더 빨리 풀었을 것 같다.
  • 경우의 수 다 구해서 바로 그 함수 내에서 어떻게 연결되어있는가를 어떻게 찾을까 고민했다. 근데 이렇게 생각하니 조금 복잡하게 느껴졌음.
  • 생각의 전환으로 자료구조만 생각해서, 이러한 자료구조가 있을 때 이걸 어떻게 순회할까? 어떻게 연결구조를 확인할까? 이렇게 생각하면 더 쉽게 다가올 것 같다.
  • 똑같은 말인가....?
• 아무튼 연구/자소서/영어자격/캐글 등으로 바쁘고 정신없고 내 자신이 한심하게 느껴지는 가운데, 이렇게 1문제라도 풀어서 좋다ㅠㅠ.

---

참조

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