[백준 17471] 게리멘더링 (java,c++)

문제풀이

java 의 경우에는 비트마스크를 이용해서 풀어보았고, c++의 경우에는 dfs를 사용해서 풀었다.

 

7달 전에 작성한 방법과 다른방법으로 풀어보고자 비트마스크를 사용해보았다.

 

문제 풀이 방법은 구역을 다 나누어보고(완탐), 그렇게 나누었을 때 조건이 성립하는지(연결이 되는 상태인지)를 체크해준다. 

조건이 만족할시에는 최솟값 업데이트를 해준다.

 

소스코드 java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Baekjoon17471 {
    static ArrayList<Integer> adjList[];
    static int population[];
    static int numPopulation;
    static boolean visited[];
    static int minGap= Integer.MAX_VALUE;
    static int countOfNode;
    static boolean isConnected;
 
    public static void checkConnected(int groupSize, int node, int groupName, int groupInfo){
        if(groupSize == countOfNode){
            isConnected = true;
            return;
        }
        for(int i=0;i<adjList[node].size();i++) {
            int nextNode = adjList[node].get(i);
            int nextGroupName = 0;
            int num = 1 << (nextNode - 1);
            if ((groupInfo & num) == num)
                nextGroupName = 1;
            if (!visited[nextNode] && nextGroupName == groupName) {
                visited[nextNode] = true;
                countOfNode++;
                checkConnected(groupSize, nextNode, groupName, groupInfo);
            }
        }
    }
 
    public static int getGap(int groupInfo) {
        ArrayList<Integer> A = new ArrayList<>();
        ArrayList<Integer> B = new ArrayList<>();
 
        int a=0,b=0;
        for(int i=1;i<=numPopulation;i++)
            visited[i] = false;
        divideArea(groupInfo, A, B);
        if(A.isEmpty() || B.isEmpty())
            return -1;
 
        if (isAreaConnected(groupInfo, A,1)) return -1;
        if (isAreaConnected(groupInfo,B,0))return -1;
 
        for(int num : A){
            a+=population[num];
        }
        for(int num : B){
            b+=population[num];
        }
        return Math.abs(a-b);
    }
 
    public static void divideArea(int groupInfo, ArrayList<Integer> a, ArrayList<Integer> b) {
        for (int i=1;i<=numPopulation;i++){
            int num = 1<<(i-1);
            if((groupInfo & num)==num)
                a.add(i);
            else
                b.add(i);
        }
    }
 
    public static boolean isAreaConnected(int groupInfo, ArrayList<Integer> a,int groupName) {
        countOfNode = 1;
        visited[a.get(0)] = true;
        isConnected = false;
        checkConnected(a.size(), a.get(0),groupName,groupInfo);
        if(!isConnected){
            return true;
        }
        return false;
    }
 
    public static void makeAllCase(){
        //0인 경우랑 전체가 1인경우 제외
        for(int i=1;i<(1<<numPopulation)-1;i++){
            int gap = getGap(i);
            if(gap>=0)
                minGap = Math.min(minGap, gap);
        }
    }
 
    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        numPopulation = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        adjList = new ArrayList[numPopulation+1];
        population = new int[numPopulation+1];
        visited = new boolean[numPopulation+1];
 
        for(int i=1;i<=numPopulation;i++) {
            population[i] = Integer.parseInt(st.nextToken());
        }
        for(int i=1;i<=numPopulation;i++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            adjList[i] = new ArrayList<Integer>();
            for (int j = 0; j < n; j++) {
                adjList[i].add(Integer.parseInt(st.nextToken()));
            }
        }
 
    }
    public static void main(String[] args) throws IOException {
        input();
        makeAllCase();
        if(minGap==Integer.MAX_VALUE)
            System.out.println("-1");
        else
            System.out.println(minGap);
    }
}
 

 

소스코드 c++

 

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <math.h>
#include <bitset>
#include <limits.h>
using namespace std;
 
typedef struct NodeInfo {
    int n_people;
    int group;
    int visited;
    NodeInfo(int p,int v,int g) {
        n_people = p;
        visited = v;
        group = g;
    }
}NodeInfo;
 
int min_result = INT_MAX;
int num_node;
vector<vector<int>> graph;
vector<NodeInfo> node_info;
int sum;
int flag;
int cnt_node;
 
void init_visited();
void check_connection(int group_size, int node, int group_name);
int check_possible();
void dfs(int index, int cnt);
int main() {
    //freopen("Text.txt", "r", stdin);
    scanf("%d", &num_node);
 
    node_info.push_back(NodeInfo(0, 0,0)); //1부터시작하려고 0에아무값 넣음.
    for (int i = 0; i < num_node; i++) {
        int temp;
        scanf("%d", &temp);
        node_info.push_back(NodeInfo(temp, 0,0));
    }
    vector<int> x;
    graph.push_back(x);
    for (int i = 0; i < num_node; i++) {
        int graph_size;
        vector<int> temp;
        int input;
        scanf("%d", &graph_size);
        for (int i = 0; i < graph_size; i++) {
            scanf("%d", &input);
            temp.push_back(input);
        }
        graph.push_back(temp);
    }
    init_visited();
    dfs(1, 0);
    if (min_result == INT_MAX)
        printf("-1\n");
    else
        printf("%d\n",min_result);
}
void init_visited() {
    for (int i = 1; i < node_info.size(); i++) {
        node_info[i].visited = 0;
    }
}
 
void check_connection(int group_size,int node,int group_name) {
    if (group_size == cnt_node) {
        flag = 0;
        return;
    }
    for (int i = 0; i < graph[node].size(); i++) {
        if (node_info[graph[node][i]].visited==0 && node_info[graph[node][i]].group==group_name) {
            node_info[graph[node][i]].visited = 1;
            cnt_node++;
            check_connection(group_size,graph[node][i], group_name);
        }
    }
}
 
int check_possible() {
    vector<int> A, B;
    int a=0;
    int b=0;
    init_visited();
    for (int i = 1; i <=num_node; i++) {
        if (node_info[i].group == 1)
            A.push_back(i);
        else {
            B.push_back(i);
        }
    }
    if (A.size() == 0 || B.size() == 0)
        return -1;
    
    flag = 1;
    node_info[A[0]].visited = 1;
    cnt_node = 1;
    check_connection(A.size(), A[0], 1);
    if (flag) {
        return -1;
    }
    flag = 1;
    node_info[B[0]].visited = 1;
    cnt_node = 1;
    check_connection(B.size(), B[0], 0);
    if (flag) {
        return -1;
    }
    for (int i = 0; i < A.size(); i++) {
        a += node_info[A[i]].n_people;
    }
    for (int i = 0; i < B.size(); i++) {
        b += node_info[B[i]].n_people;
    }
    return abs(a-b);
 
}
 
void dfs(int index,int cnt ) {
    //종료조건
    if (cnt >= 1&&cnt<num_node) //최소 1개이상의 원소만 뽑으면 계산해주니까
    {
        //나뉠수 있는지 체크후
        int val = check_possible();
        if (val>=0) {
            min_result = min(val, min_result);
        }
        //최솟값 계산
    }
 
    //
    for (int i = index; i <=num_node; i++) {
        if (node_info[i].group == 1) {
            continue;
        }
        node_info[i].group = 1;
        dfs(i, cnt + 1);
        node_info[i].group = 0;
    }
    
}

문제 링크 : www.acmicpc.net/problem/17471

17471번: 게리맨더링