[17471] 게리맨더링 in Java

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

17471번: 게리맨더링

 

 

---

문제 요약

선거구 : 2개 (1개의 구역이라도 포함해야함, 한 선거구 내에 있는 구역은 모두 연결되어있어야함, 다른 선거구의 구역과는 연결될 수 없다.)
구역 : N개 (각 구역은 2개의 선거구 중 하나에 포함되어야한다.)
같은 선거구 내에서 A-C-B , A가 B랑 바로 연결되는 게 아니더라도, 또다른 인접한 구역을 통해 갈 수 있다면?
두 구역(A,B)는 연결되어있다고 할 수 있다.


두 선거구에 포함된 인구의 차이를 최소로 한다.

 

---

입력

입력방식을 이해못해서 헤맸던 문제

구역의 개수 = 첫번째 줄

각 구역의 인구 = 2번째 줄

각 구역과 인접한 구역의 정보 = N개의 줄 

(개수, 해당 구역과 연결된 구역의 번호(개수만큼))

 

6
5 2 3 4 1 2
2 2 4 -> 1번과 연결되어있는 정점(2,4)
4 1 3 6 5 -> 2번과 연결되어 있는 정점(1,3,6,5)
2 4 2 -> 3번과 연결되어 있는 정점 (2,4)
2 1 3 -> 4번과 연결되어 있는 정점 (1,3)
1 2 -> 5번과 연결되어 있는 정점 (2)
1 2 -> 6번과 연결되어 있는 정점 (2)

---

접근 방식

1. A선거구에 해당하는 구역을 조합을 이용하여 구한다.

1개의 구역을 뽑을때, 2개의 구역을 뽑을때 -> for문을 이용하여 comb 함수를 호출한다.

 

 

2. 뽑은 구역이 모두 연결되어 있는지 A팀, B팀 구역을 모두 확인한다. -> isConnect

 

 

3. 연결되어 있다면 각 팀별로 인구수를 구하고, A팀과 B팀의 인구수 차이를 구한다.

 

 

 

 

---

시행 착오

해당 문제에서는 각 구역과 연결된 인접한 구역의 정보를

이중 List에 받으려고 했으나

이중 List를 선언하는 방식에 대해 낯설어서 헤맸다.

 

리스트의 타입을 정수형 리스트로 선언해주면,

리스트 안에 리스트를 넣을 수 있고

2차원 배열로 만들 수 있다.

 

int r=3;
List<List<Integer>> map = new ArrayList<>(); // 요소로 정수형 리스트가 들어오는 리스트
for(int i=0; i<r; i++){
    map.add(new ArrayList<>()); // 1차원 배열 요소로 비어 있는 1차원 배열을 넣어준다 = > 2차원 배열이 된다

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static int N; // 구역의 개수
    static int[] people; // 구역의 인구수
    static List<List<Integer>> map; // 인접 구역의 정보 (2차원 리스트)
    static boolean[] selected;
    static int answer;
    
    
    public static boolean isConnect(int size, ArrayList<Integer> array) {
        boolean[] visited=new boolean[N+1]; // A팀 방문구역
        int allCnt=1; 
        Queue<Integer> queue= new LinkedList<>();
        queue.add(array.get(0));
        visited[array.get(0)]=true;
        
        while(!queue.isEmpty()) {
            int start= queue.poll(); // 시작 노드
            for (int i : map.get(start)) {
                if (!visited[i] && array.contains(i)) {
                    queue.add(i);
                    allCnt++;
                    visited[i]=true;
                }
            }
        }
        if (size==allCnt) return true;
        return false;
        
    }
    
    public static void comb(int cnt, int start) {
        if (cnt==0) {
            ArrayList<Integer> teamA=new ArrayList<>();
            ArrayList<Integer> teamB=new ArrayList<>();
            for (int i = 1; i <= N; i++) {
                if (selected[i]) teamA.add(i);
                else teamB.add(i);
            }
            // 2. A팀, B팀이 각각 연결 되어 있는지 확인
            if (isConnect(teamA.size(),teamA) && isConnect(teamB.size(), teamB)) {                
                // 3. 연결 되어 있다면 인구 차이 계산
                int valA=0, valB=0;
                for (int a : teamA) {
                    valA+=people[a];
                }
                for (int b : teamB) {
                    valB+=people[b];
                }
                answer=Math.min(answer, Math.abs(valA-valB));
            }
            return;
        }
        for (int i = start; i <= N; i++) {
            selected[i]=true;
            comb(cnt-1,i+1);
            selected[i]=false;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N= Integer.parseInt(br.readLine()); // 구역의 개수
        people=new int[N+1]; // 구역의 인구수
        map=new ArrayList<>(); 
        answer=Integer.MAX_VALUE;
        selected=new boolean[N+1];
        
        // 맵 크기 초기화
        for (int i = 0; i <=N; i++) {
            map.add(new ArrayList<>());
        }
        
        // 인구 정보 입력 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int j = 1; j <= N; j++) {
            people[j]=Integer.parseInt(st.nextToken());
        }
        // 인접한 구역 정보 입력 받기
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int size = Integer.parseInt(st.nextToken()); 
            for (int j = 0; j < size; j++) {
                map.get(i).add(Integer.parseInt(st.nextToken()));
            }
        }
        
        // 1. 조합으로 구역 나누기
        for (int i = 1; i < N; i++) {
            comb(i,1); // cnt, start
        }
        
        if(answer==Integer.MAX_VALUE) {
            System.out.println(-1);
        }else {
            System.out.println(answer);
        }
    }
}