[백준]17471번 - 게리맨더링 JAVA 풀이

백준 17471번 게리맨더링 JAVA 풀이

문제

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

17471번: 게리맨더링

 

 

해당 문제는 입력이 좀 헷갈렸다. 예제입력 1을 예시로, 

1번 노드 - 2개 노드와 연결되어 있고 2 4 와 연결 

2번 노드 - 4 개 노드와 연결되어 있고 1 3 6 5 와 연결

3번 노드 - 2개 노드와 연결되어 있고 4 2 와 연결

4번 노드 - 2개 노드와 연결되어 있고 1 3 와 연결

5번 노드-  1개 노드와 연결되어 있고 1 과 연결

6번 노드 - 1개 노드와 연결되어 있고 1 과 연결

이다. 

 

해당 문제는 모든 지역구를 두 개의 선거구로 할당하는 것부터 시작한다. 해당 풀이에서는 dfs를 통해서 모든 노드를 1번 선거구, 2번 선거구로 할당했다. 

 private static void divide_area(int depth) {
        for(int i=0; i<N; i++){
            if(division[i]==0 || division[i]==2){ //만약 선거구가 아직 나눠지지 않은 경우에
                division[i]=1; //1번 선거구로 지정
                dfs(i, depth +1); //dfs 실행
                division[i]=0; //1번 선거구로 지정한 것을 다시 풀어줌
            }
        }
    }

 

선거구를 나누는 작업은 모든 지역의 수인 N 의 반 만큼만 하면 된다. N/2개의 지역이 특정 선거구로 지정되면 나머지 지역들은 자동으로 다른 선거구로 지정되기 때문이다. 또한, 두 선거구의 인구 수 차이를 구하는 것이기 때문에 111/222 든 222/111 이든 똑같은 인구수 차이를 보인다.

 if(depth>N/2){ //depth가 N/2일 때 dfs는 return 된다.
            //선거구를 두 개로 나누고 인구수 차를 계산하는 것이기 때문에 N/2에 return 한다.
            //1-3 이 1번 구역, 4-6이 2번 구역일 때와 4-6이 1번 구역, 1-3이 2번 구역일 때의 그 인구수 차는 똑같기 때문이다.
            return;
        }

 하나의 선거구에 모든 지역이 배정되어서는 안된다. 

  int count=0;
        for(int i=0; i<N; i++){
            if(division[i]==0){
                division[i]=2;
                count++;
            } //한 선거구에 모든 지역이 포함되는 경우를 찾는다. count가 N이면 모든 지역이 하나의 선거구에 속하게 된다.
        }

모든 지역을 두 개 이상의 선거구에 지정했다면 이제 각 선거구의 지역들이 서로 이어져 있는지 확인한다.

if(count!=N){
            //division 1 검사
            boolean link1=bfs(division,1);
            //division 2 검사
            boolean link2= bfs(division,2);

   private static boolean bfs(int[] division, int n) {
        int[] bfs_visited= new int[N]; //연결된 노드를 방문했는지 하지 않았는지 확인하기 위한 배열
        Queue<Integer> queue = new ArrayDeque<>();
        for(int i=0; i<N; i++){
            if(division[i]==n){ // 지정 선거구인 n번 선거구 중 하나를 queue에 삽입
                queue.add(i);
                bfs_visited[i]=n;
                break;
            }
        }
        while(!queue.isEmpty()){
            int div= queue.poll();
            for(int i=1; i<N; i++){
               if(division[i]==n) { //지정 선거구인 n번 선거구인 경우에만 아래 로직을 실행
                   if (area[div][i] == 1 && bfs_visited[i]==0) { //만약 i번 선거구에 아직 방문하지 않았고, 이전 선거구와 연결되어 있다면
                       queue.add(i); //큐에 i번 지역을 추가
                   }
                   if(area[div][i] == 1){ //이전 선거구와 연결되어 있다면 방문한다.
                       bfs_visited[i] = n;
                   }
               }
            }
        }
        if (check_unconnected(division, n, bfs_visited)) return false;
        return true;
    }

    private static boolean check_unconnected(int[] division, int n, int[] bfs_visited) {
        for(int i=0; i<N; i++){
            if(division[i]== n){ //만약 지정 선거구인 n번 선거구 안에서
                if(division[i]!= bfs_visited[i]){ //연결이 끊어져 있는 지역들이 존재한다면
                    return true;
                }
            }
        }
        return false;
    }

선거구는 1번, 2번으로 나누어질 것이기 때문에 1번 선거구에 대해서 모든 지역이 다 연결되어 있는지 먼저 체크한다. 

선거구가 1번인 경우의 지역을 하나 찾아내서 queue에 삽입하고, 방문처리 한다.

그리고 queue가 빌 때 까지 queue에서 선거구가 1번인 지역 하나를 뽑고, 해당 지역과 연결된 지역을 찾아서 방문했는지 확인 후 queue에 넣는다. 그리고 방문처리 한다.

만약 1번 선거구인 지역들이 모두 방문되었다면 해당 지역들은 모두 이어져있다는 뜻이다. 반대로, 방문되지 않은 지역이 선거구에 포함되어 있다면, 해당 선거구는 서로서로 연결되어있지 않다는 뜻이다. 

해당 작업을 2번 선거구 데이터에도 적용한다. 

 

만약 1번 선거구와 2번 선거구가 각각의 지역들과 모두 연결되어 있는 상태라면 선거구들의 인구수 차이를 구한다.  

       int area1=0; //1번 선거구 인구수
            int area2=0; //2번 선거구 인구수
            if(link1 && link2){ //만약 1번 선거구의 모든 지역이 이어져 있고, 2번 선거구의 모든 지역이 이어져 있다면
                for(int i=0; i<N; i++){
                    if(division[i]==1){
                        area1+= population[i]; //1번 선거구의 인구수를 누적함.
                    }
                    else if(division[i]==2){
                        area2+= population[i]; //2번 선거구의 인구수를 누적함.
                    }
                }
                int area_min = Math.abs(area1-area2); //두 선거구의 인구수 차이를 계산함.
                if(area_min < min){ //지금까지 보인 인구수 차이보다 지금의 인구수 차이가 더 작다면 갱신
                    min= area_min;
                }
            }

 

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
    static int N;
    static int[][] area;
    static int[] population;
    static int min = 99999999;
    static int[] division;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        area = new int[N][N];
        population = new int[N];
        division= new int[N];

        //input process start
        String[] input = br.readLine().split(" ");
        for (int i = 0; i < input.length; i++) {
            population[i] = Integer.parseInt(input[i]);
        }

        for (int i = 0; i < N; i++) {
            input = br.readLine().split(" ");
            int num = Integer.parseInt(input[0]);
            for (int j = 1; j <= num; j++) {

                area[i][Integer.parseInt(input[j])-1] = 1;
                area[Integer.parseInt(input[j])-1][i] = 1;
            }
        }
        //input process end

        //main logic start
        dfs(0,0);
        //main logic end

        //result process start
        if(min==99999999){
            System.out.println(-1);
        }
        else{
            System.out.println(min);
        }
        //result process end
    }


    public static void dfs(int n, int depth){
        if(depth>N/2){ //depth가 N/2일 때 dfs는 return 된다.
            //선거구를 두 개로 나누고 인구수 차를 계산하는 것이기 때문에 N/2에 return 한다.
            //1-3 이 1번 구역, 4-6이 2번 구역일 때와 4-6이 1번 구역, 1-3이 2번 구역일 때의 그 인구수 차는 똑같기 때문이다.
            return;
        }
        int count=0;
        for(int i=0; i<N; i++){
            if(division[i]==0){
                division[i]=2;
                count++;
            } //한 선거구에 모든 지역이 포함되는 경우를 찾는다. count가 N이면 모든 지역이 하나의 선거구에 속하게 된다.
        }

        if(count!=N){
            //division 1 검사
            boolean link1=bfs(division,1);
            //division 2 검사
            boolean link2= bfs(division,2);

            int area1=0; //1번 선거구 인구수
            int area2=0; //2번 선거구 인구수
            if(link1 && link2){ //만약 1번 선거구의 모든 지역이 이어져 있고, 2번 선거구의 모든 지역이 이어져 있다면
                for(int i=0; i<N; i++){
                    if(division[i]==1){
                        area1+= population[i]; //1번 선거구의 인구수를 누적함.
                    }
                    else if(division[i]==2){
                        area2+= population[i]; //2번 선거구의 인구수를 누적함.
                    }
                }
                int area_min = Math.abs(area1-area2); //두 선거구의 인구수 차이를 계산함.
                if(area_min < min){ //지금까지 보인 인구수 차이보다 지금의 인구수 차이가 더 작다면 갱신
                    min= are1a_min;
                }
            }
        }
        //전체 선거구를 1번, 2번으로 나누는 부분.
        divide_area(depth);
    }

    private static void divide_area(int depth) {
        for(int i=0; i<N; i++){
            if(division[i]==0 || division[i]==2){ //만약 선거구가 아직 나눠지지 않은 경우에
                division[i]=1; //1번 선거구로 지정
                dfs(i, depth +1); //dfs 실행
                division[i]=0; //1번 선거구로 지정한 것을 다시 풀어줌
            }
        }
    }

    private static boolean bfs(int[] division, int n) {
        int[] bfs_visited= new int[N]; //연결된 노드를 방문했는지 하지 않았는지 확인하기 위한 배열
        Queue<Integer> queue = new ArrayDeque<>();
        for(int i=0; i<N; i++){
            if(division[i]==n){ // 지정 선거구인 n번 선거구 중 하나를 queue에 삽입
                queue.add(i);
                bfs_visited[i]=n;
                break;
            }
        }
        while(!queue.isEmpty()){
            int div= queue.poll();
            for(int i=1; i<N; i++){
               if(division[i]==n) { //지정 선거구인 n번 선거구인 경우에만 아래 로직을 실행
                   if (area[div][i] == 1 && bfs_visited[i]==0) { //만약 i번 선거구에 아직 방문하지 않았고, 이전 선거구와 연결되어 있다면
                       queue.add(i); //큐에 i번 지역을 추가
                   }
                   if(area[div][i] == 1){ //이전 선거구와 연결되어 있다면 방문한다.
                       bfs_visited[i] = n;
                   }
               }
            }
        }
        if (check_unconnected(division, n, bfs_visited)) return false;
        return true;
    }

    private static boolean check_unconnected(int[] division, int n, int[] bfs_visited) {
        for(int i=0; i<N; i++){
            if(division[i]== n){ //만약 지정 선거구인 n번 선거구 안에서
                if(division[i]!= bfs_visited[i]){ //연결이 끊어져 있는 지역들이 존재한다면
                    return true;
                }
            }
        }
        return false;
    }
}