[개쉬운 풀이] 백준 17471 게리맨더링

728x90

문제

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

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

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

생각

가장 먼저 든 생각은 N개의 구역을 두 개의 선거구로 나누어야 한다는 것이었다. 이 부분에서 조합법을 사용해야 한다고 판단했다. 또한 주어진 입력의 최대가 10을 확인하고 완전탐색을 통해 해결해야 한다고 확신했다. 문제를 통해 주어진 조건과 풀이의 흐름은 다음과 같다.

N개의 구역을 두 선거구로 나누기
1. (주의) 한 선거구의 크기가 0이 되서는 안된다.
각 선거구 a, b가 각각 연결된 상태인지 확인하기
1. 각 선거구끼리는 연결될 필요가 없다 (ex -> A선거구와 B선거구는 연결되지 않아도 된다.)
각 선거구의 인구수 합하기
두 선거구의 인구 차이 구하기
나올 수 있는 경우의 수 중 최소의 인구 차이 구하기

이 부분에서 1번 조건은 dfs를 통해서 해결하였고 2번은 bfs를 통해 연결된 상태를 체크하면서 해결하였다. 예외를 고려하며 해결해 보자.

코드

vector<int> people;
vector<vector<int>> map;

void input(){
    cin >> N;
    //각 구역별 사람들의 수를 0번부터 담아주었다.
    for(int i = 0; i < N; i++){
        int t;
        cin >> t;
        people.push_back(t);
    }
    //맵의 크기를 설정
    map.resize(N+1,vector<int>());
    
    //각 구역이 연결된 상태를 2중 벡터로 저장하였다.
    for(int i = 1; i <= N; i++){
        int size;
        cin >> size;
        for(int j = 0; j < size; j++){
            int t;
            cin >> t;
            map[i].push_back(t);
        }
    }
}

입력 형식을 고려하여 설계하였다. 나중에 isConnected()에서 bfs()를 활용하기 위해 2중 벡터로 저장하였다. 또한 문제에서 양방향 연결을 입력해 주기 때문에 따로 추가로 양방향으로 저장하지 않았다.

bool selected[MAX];

//dfs를 활용하여 2개의 군집으로 생성한다.
void dfs(int start, int depth){
	//군집에 최소 인원이 필요하지 않으므로 depth는 1부터 계산한다.
    if(depth >= 1){
        auto T = makeCombination(); 
        sol(T); 
    }
    //dfs형태
    for(int i = start; i <= N; i++){
        if(selected[i]) continue;
        selected[i] = true;
        dfs(i + 1, depth + 1);
        selected[i] = false;
    }
}

1. 두 개의 군집을 형성하기 위해 dfs를 통해 selected에 군집에 들어갈 원소를 true로 판단하고 makeCombination() 함수를 통해서 각각 vector <int> a와 vector<int> b로 담아주었다.

//두 개의 vector를 반환한다. 
pair<vector<int>,vector<int>> makeCombination(){
    vector<int> a;
    vector<int> b;
    for(int i = 1; i <= N; i++){
        if(selected[i]) a.push_back(i);
        else b.push_back(i);
    }
    return make_pair(a,b);
}

// 전체적인 2~4번에 해당하는 코드이다.
void sol(pair<vector<int>,vector<int>> result){
    vector<int> a = result.first;
    vector<int> b = result.second;
    if(isConnected(a) && isConnected(b)){
    	//(중요) 연결되지 않아 최소값을 구할 수 없으면 -1을 출력해주어야하는데 
        //findAnswer 변수를 통해 판단한다.
        //한번이라도 되면 answer 출력, 아니면 -1 출력
        findAnswer = true; 
        int tmp = teamDiff(a,b);
        if(answer > tmp) answer = tmp;
    }
    
}

dfs()에서 조합으로 만든 결과를 makeCombination에서 vector에 담고 sol()로 보내주어 2~4번 조건을 확인한다.

bool visited[MAX];

//v라는 vector가 연결된 상태인가?
bool isConnected(vector<int> v){
	//숨겨진 조건인 선거구에 구역이 없을 경우를 배제한다.
    if(v.empty()) return false;
    
    //초기화
    memset(visited, true, sizeof(visited));
    
    //고려해야할 원소들만 visited에 false로 초기화하였다.
    for(int i = 0; i < v.size(); i++){
        visited[v[i]] = false;
    }
	
    //bfs는 queue를 사용하여서 해결한다.
    int node = v[0]; //처음 값 넣어줌
    queue<int> q;
    visited[node] = true;
    q.push(node);
    
    while(!q.empty()){
        node = q.front();
        q.pop();
        
        //현재 구역 node에 연결된 모든 값들을 확인한다.
        for(int i = 0; i < map[node].size(); i++){
            int x = map[node][i];
			//x가 방문했다면 넘어간다.
            if(visited[x]) continue;
            visited[x] = true;
            q.push(x);
        }
    }
    
    //해당 포문을 통해서 만약 방문이 되지 않았다면 해당 선거구는 모두 연결된 것이 아니다.
    for(int i = 0; i < MAX; i++){
        if(!visited[i]) return false;
    }
    return true;
}

처음에 isConnected() 함수를 구상하면서 고려한 부분은

1. bfs()를 진행하면서 방문했던 구역 재방문하지 않기

2. 해당 선거구 v에 포함되지 않는 구역을 통해서 방문하지 않기

였다. 그래서 초기에 둘을 따로 bool 형태의 배열을 통해서 선언을 했지만 다시 생각해 보니 visited에 고려해야 할 원소들(해당 선거구 v의 원소들)만 다시 false로 초기화하여 생각했더니 1번과 2번이 동시에 해결되었다.

int teamPeople(vector<int> v){
    int result = 0;
    for(int i = 0; i < v.size(); i++){
	    //people에 0번째 인덱스부터 각 구역에 인구수를 저장하였으므로
        //헷갈리지 않고 -1을 해주자.
        result += people[v[i]-1]; 
    }
    return result;
}

int teamDiff(vector<int> a, vector<int> b){
    int aPeople = teamPeople(a);
    int bPeople = teamPeople(b);
    return abs(aPeople - bPeople);
}

4~5번 조건에 해당하는 코드이다.

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <cmath>
#include <queue>
#define MAX 11
using namespace std;

int N;
vector<int> people;
vector<vector<int>> map;
bool selected[MAX];
bool visited[MAX];
int answer = 10e8;
bool findAnswer = false;

void input(){
    cin >> N;
    for(int i = 0; i < N; i++){
        int t;
        cin >> t;
        people.push_back(t);
    }
    map.resize(N+1,vector<int>());

    for(int i = 1; i <= N; i++){
        int size;
        cin >> size;
        for(int j = 0; j < size; j++){
            int t;
            cin >> t;
            map[i].push_back(t);
        }
    }
}

bool isConnected(vector<int> v){
    if(v.empty()) return false;
    memset(visited, true, sizeof(visited));
    for(int i = 0; i < v.size(); i++){
        visited[v[i]] = false;
    }

    int node = v[0];
    queue<int> q;
    visited[node] = true;
    q.push(node);
    while(!q.empty()){
        node = q.front();
        q.pop();
        for(int i = 0; i < map[node].size(); i++){
            int x = map[node][i];

            if(visited[x]) continue;
            visited[x] = true;
            q.push(x);
        }
    }
    for(int i = 0; i < MAX; i++){
        if(!visited[i]) return false;
    }
    return true;
}

pair<vector<int>,vector<int>> makeCombination(){
    vector<int> a;
    vector<int> b;
    for(int i = 1; i <= N; i++){
        if(selected[i]) a.push_back(i);
        else b.push_back(i);
    }
    return make_pair(a,b);
}

int teamPeople(vector<int> v){
    int result = 0;
    for(int i = 0; i < v.size(); i++){
        result += people[v[i]-1];
    }
    return result;
}

int teamDiff(vector<int> a, vector<int> b){
    int aPeople = teamPeople(a);
    int bPeople = teamPeople(b);
    
    return abs(aPeople - bPeople);
}

void sol(pair<vector<int>,vector<int>> result){
    vector<int> a = result.first;
    vector<int> b = result.second;
    if(isConnected(a) && isConnected(b)){
        findAnswer = true;
        int tmp = teamDiff(a,b);
        if(answer > tmp) answer = tmp;
    }
    
}

void dfs(int start, int depth){
    if(depth >= 1){
        auto T = makeCombination();
        sol(T);
    }
    for(int i = start; i <= N; i++){
        if(selected[i]) continue;
        selected[i] = true;
        dfs(i + 1, depth + 1);
        selected[i] = false;
    }
}

int main(){
    input();
    memset(selected,false,sizeof(selected));
    dfs(1,0);
    
    //아까 설명한 findAnswer을 통해 최종 결과를 출력한다.
    if(findAnswer)cout << answer << endl;
    else cout << -1 << endl;
    return 0;
}

천천히 주어진 조건과 풀이 과정을 이해하면 쉽게 풀 수 있지만 isConnected와 군집 조합을 구현하는데 집중을 해야 한다.

결론

bfs()를 하는데 queue를 사용할 수 있다.
dfs()를 통해 조합을 구현할 수 있다.
memset()을 알아놓자.

실패했을 때 고려해야 할 것

1. 두 선거구는 연결이 되지 않아도 된다. -> 선거구 내에서만 연결 상태면 된다.

2. 선거구를 만들 수 없는 경우는 -1을 출력해야 한다.

3. 1~N까지의 선거구를 사용하므로 배열을 사용할 때 인덱스와 번호가 맞는지 확인하자.

4. 초기화를 정확하게 했는지 판단하자.

5. 두 선거구 인원의 차이를 구하므로 abs()를 활용하자.

728x90

'알고리즘 문제 > DFS' 카테고리의 다른 글

[개쉬운 풀이] 백준 12100 2048 (Easy) CPP (20일차) (0)	2024.12.12
[개쉬운 풀이] 백준 19542 전단지 돌리기 (1)	2024.10.16
[개쉬운 풀이] 백준 2668 숫자고르기 (0)	2024.08.05

힘든 취업장에서 살아남는 법

[개쉬운 풀이] 백준 17471 게리맨더링

문제

생각

코드

전체 코드

결론

실패했을 때 고려해야 할 것

'알고리즘 문제 > DFS' 카테고리의 다른 글

티스토리툴바

[개쉬운 풀이] 백준 17471 게리맨더링

문제

생각

코드

전체 코드

결론

실패했을 때 고려해야 할 것

'알고리즘 문제 > DFS' 카테고리의 다른 글

관련글

티스토리툴바