SW 역량 테스트 A형 기출 문제 (게리맨더링)

[게리맨더링 _ 17471]

 

 

* 조건

1. 구역의 개수 N (2<= N <= 10)이 주어진다
2. 1부터 N까지 각각 갖는 인구의 값이 주어진다
3. 1부터 N까지 인접해있는 구역의 정보가 주어진다 (인접행렬)
4. 선거구는 2개로 나눈다
   • 팀을 만들었을 때 해당 선거구는 서로 연결되어 있어야 한다
   • 연결되어있지 않다면 선거구가 될 수 없다
5. 두 선거구로 나누었을 때 만들 수 있는 최소 인구 차를 구한다

* 알고리즘

• 팀을 조합해야한다: DFS
• 조합된 팀이 연결되어있는지 확인: BFS

* 로직(Logic)

• 주어진 정보를 활용해 인접행렬로 만든다
• 팀을 조합한다
  • 선거구 A를 0으로 설정
  • 선거구 B를 1로 설정
• 조합을 한 뒤 각 팀별로 연결이 되어있는지 판단한다
  • 해당 팀의 출발지만 찾고 큐에 넣는다
  • 큐를 기반으로 인접한 곳을 마킹한다
  • 선거구는 같지만 마킹이 안되어있다면 모순이기 때문에 false 리턴
• 두 팀 모두 연결이 제대로 연결되어 있다면 최소 인구 차를 계속해서 덮어나간다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Location {
    public int people;  //인구

    public Location(int people) {
        this.people = people;
    }
}

public class Problem_17471 {

    static int N;   //구역의 개수
    static Location[] locations;
    static int[][] matrix;  //인접행렬

    static int[] team;
    static boolean[] checked;
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        locations = new Location[N+1];  //1~N까지
        matrix = new int[N+1][N+1];
        team = new int[N+1];

        String input_people = br.readLine();
        st = new StringTokenizer(input_people, " ");
        int size = st.countTokens();
        for(int i=1; i<=size; ++i){
            locations[i] = new Location(Integer.parseInt(st.nextToken()));
        }

        for(int i=1; i<=N; ++i){
            String input = br.readLine();
            st = new StringTokenizer(input, " ");
            int adjNum = Integer.parseInt(st.nextToken());  //인접한 곳의 개수
            for(int a=0; a<adjNum; ++a){
                int node = Integer.parseInt(st.nextToken());
                matrix[i][node] = 1;
                matrix[node][i] = 1;
            }
        }

        //팀이 만들어지면 -> 해당 팀들이 링크에 속한지 아닌지 판단 -> 속한다면 최솟값으로 덮어주기
        int index = 1;
        makeTeam(index);

        if(answer == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(answer);
    }

    private static void makeTeam(int index) {
        if(index == N+1){
            //각 팀들(A, B)이 연결되어있는지 판단
            if(isLinked(0) && isLinked(1)){

                //다 속한다면 최솟값 덮어주기
                int people = getTeamPeople();   //각 팀의 인구 차이
                answer = Math.min(answer, people);
            }
            return;
        }

        //0이면 A팀, 1이면 B팀
        team[index] = 0;
        makeTeam(index+1);

        team[index] = 1;
        makeTeam(index+1);

    }

    private static int getTeamPeople() {
        int peopleA = 0;
        int peopleB = 0;
        for(int i=1; i<=N; ++i){
            if(team[i] == 0) peopleA += locations[i].people;
            else if(team[i] == 1) peopleB += locations[i].people;
        }

        return Math.abs(peopleA - peopleB);
    }

    private static boolean isLinked(int teamIdx) {
        checked = new boolean[N+1];
        Queue<Integer> queue = new LinkedList<>();

        for(int i=1; i<=N; ++i){
            //같은 팀들을
            if(team[i] == teamIdx){
                queue.offer(i);
                checked[i] = true;
                break;
            }
        }

        //인접한 부분을 마킹시켜줌
        while (!queue.isEmpty()){
            int q = queue.poll();
            for(int a=1; a<=N; ++a){
                if(!checked[a] && team[a] == teamIdx && matrix[q][a] == 1) {
                    queue.offer(a);
                    checked[a] = true;
                }
            }
        }

        //같은 팀은 맞는데 마킹(check)이 안되어있다면 모순
        for(int i=1; i<=N; ++i){
            if(team[i] == teamIdx && !checked[i]){
                return false;
            }
        }

        return true;
    }
}