[알고리즘] 17471. 게리맨더링

0. 문제

 

17471번: 게리맨더링

 

---

1. 문제 이해

 

1. 부분집합
2. 완전탐색 (DFS, BFS)

 

---

2. 제출

 

가. 통과

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ17471 {

    static int N, ret;
    static int[] person, parent;
    static List<Integer>[]  g; // 인접 리스트
    static List<List<Integer>> groups;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        ret = Integer.MAX_VALUE;
        int end = N+1;

        // 인구 수 저장
        st = new StringTokenizer(br.readLine());
        person = new int[end];
        for(int i=1; i<end; i++) {
            person[i] = Integer.parseInt(st.nextToken());
        }

        // 인접 리스트
        int num; // 연결된 구역의 수
        g = new ArrayList[end];
        for(int i=1; i<end; i++) {
            g[i] = new ArrayList<Integer>();
            st = new StringTokenizer(br.readLine());
            num = Integer.parseInt(st.nextToken());
            for(int j=0; j<num; j++) {
                g[i].add(Integer.parseInt(st.nextToken()));
            }
        }

        solve();

        System.out.println(ret);
        br.close();
    }

    static void solve() {
        groups = new ArrayList<>();
        // 전체에 대하여 연결된 구역의 수를 구한다.
        List<Integer> group;
        boolean[] vis = new boolean[N+1];
        for(int i=1; i<N+1; i++) {
            if(vis[i]) continue;
            group = new ArrayList<Integer>();
            dfs(i, vis, group);
            groups.add(group);
        }

        // 두 선거구로 나눌 수 없는 경우
        if(groups.size() > 2) {
            ret = -1;
            return;
        }else if(groups.size() == 2){ // 이미 두 선거구인 경우
            ret = Math.abs(count(groups.get(0)) - count(groups.get(1)));
            return;
        }else { // 모든 선거구가 연결되어있을 때
            divide();
        }
    }

    private static void divide() { // 2개의 선거구로 나누고 인구 차이의 최소값 찾기
        List<Integer> g1 = new ArrayList<Integer>();
        List<Integer> g2 = new ArrayList<Integer>();
        int tmp;
        int end = 1<<N;
        next : for(int comb=0; comb<end; comb++) { // 부분집합 : 바이너리카운팅
            if(comb == 0 || comb == end-1) continue; // 몰빵 방지
            g1 = new ArrayList<Integer>(); // 1번 선거구
            g2 = new ArrayList<Integer>(); // 2번 선거구
            for(int j=0; j<N; j++) {
                if((comb & (1 << j)) != 0) { // 1번 선거구 
                    g1.add(j+1); // 1 ~ N
                }else { // 2번 선거구
                    g2.add(j+1); // 1 ~ N
                }
            }
            // 같은 선거구에 속한 구역은 서로 연결되어야 한다.
            groups.clear(); groups.add(g1); groups.add(g2);
            for(List<Integer> group : groups) {
                int cnt = 0;
                boolean[] vis = new boolean[N+1]; // 1 ~ N
                for(int i=0; i<group.size(); i++) {
                    int cur = group.get(i);
                    if(vis[cur]) continue;
                    if(cnt > 0) continue next; // 불가능한 선거구 조합
                    dfs2(cur, vis, group);
                    cnt++;
                }
            }

            // 모든 조건 통과 : 2개의 선거구로 나누고 각 선거구의 구역은 연결되어있다.
            //System.out.println(g1 + ", " + g2);
            tmp = Math.abs(count(g1) - count(g2)); // 양 선거구의 인구 차이 계산
            ret = Math.min(ret, tmp); // 최소 인구 차이 찾기
        }
    }

    static void dfs(int cur, boolean[] vis, List<Integer> res) {
        vis[cur] = true;
        res.add(cur);

        for(Integer next : g[cur]) {
            if(vis[next]) continue;
            dfs(next, vis, res);
        }
    }

    static void dfs2(int cur, boolean[] vis, List<Integer> group) {
        vis[cur] = true;

        for(Integer next : g[cur]) {
            if(vis[next]) continue;
            if(!group.contains(next))continue; // 같은 선거구가 아니면 못지나간다. 
            dfs2(next, vis, group);
        }
    }

    static int count(List<Integer> list) {
        int cnt = 0;

        for(Integer i : list) {
            cnt += person[i];
        }

        return cnt;
    }

}

• 통과는 했지만 좋은 코드는 아닌 것 같다.
• dfs와 dfs2로 비슷한 동작을 수행하는 메서드가 두 개나 존재한다.

 

solve()에서 가능한 부분집합이 없거나 하나인 경우를 빠르게 걸러낼 생각이었다.

 

하지만 실제 구현하고 보니 시간복잡도도 상승하고 코드도 더 많이 복잡해졌다.

 

---

나. 개선

 

• 가능한 부분집합이 없거나 하나인 경우를 빠르게 걸러내기 위해서 별도의 dfs 탐색을 수행하지 않는다.
• 바이너리 카운팅이 아닌 재귀함수로 부분집합을 생성한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

// 불필요한 dfs 탐색을 줄이고 
// 바이너리 카운팅이 아닌 재귀 함수로 부분집합 생성
public class BOJ17471_2 {

    static int N, ret;
    static int[] people; // 인구수 저장
    static List<Integer>[] g; // 인접 리스트
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        ret = Integer.MAX_VALUE;
        people = new int[N+1]; // 1 ~ N
        g = new List[N+1];

        // 인구수 저장
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++) {
            people[i] = Integer.parseInt(st.nextToken());
        }

        // 인접 리스트 초기화
        int num;
        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            g[i] = new ArrayList<>();
            num = Integer.parseInt(st.nextToken());
            for(int j=0; j<num; j++) {
                g[i].add(Integer.parseInt(st.nextToken()));
            }
        }

        // 부분집합을 생성하고 최소 인구차를 찾는다.
        solve(1, new int[N+1]);

        if(ret == Integer.MAX_VALUE) ret = -1;
        System.out.println(ret);
        br.close();
    }

    // 재귀함수로 부분집합을 생성한다.
    static void solve(int depth, int[] comb) {
        if(depth == N+1) {
            if(!check(comb, 0) || !check(comb, 1)) return; // 한 선거구의 구역은 모두 연결되었는가?
            ret = Math.min(ret,  count(comb));
            // if(ret > count(comb)){
            //     ret = count(comb);
            //     System.out.println(Arrays.toString(comb) + " : " + ret);
            // }
            return;
        }

        // 부분집합을 생성한다.
        comb[depth] = 1;
        solve(depth+1, comb);
        // 원복
        comb[depth] = 0;
        solve(depth+1, comb);
    }

    static boolean check(int[] comb, int group) {

        int same = 0;
        for(int i=1; i<=N; i++){
            if(comb[i] == group) same++;
        }
        if(same == N) return false; // 몰빵 금지

        int cnt = 0;
        boolean[] vis = new boolean[N+1];
        for(int i=1; i<=N; i++) {
            if(comb[i] != group) continue; // 같은 선거구
            if(vis[i]) continue;
            if(cnt>0) return false; // 같은 선거구에서 연결될 수 없는 구역 존재
            dfs(i, vis, comb, group);
            cnt++;
        }
        return true;
    }

    static void dfs(int cur, boolean[] vis, int[] comb, int group) {
        vis[cur] = true;

        for(Integer next : g[cur]) {
            if(comb[next] != group) continue;
            if(vis[next]) continue;
            dfs(next, vis, comb, group);
        }
    }

    static int count(int[] comb) {
        int sum0 = 0;
        int sum1 = 0;

        for(int i=1; i<=N; i++) { // 1 ~ N
            if(comb[i] == 0) sum0 += people[i];
            if(comb[i] == 1) sum1 += people[i];
        }

        return Math.abs(sum0 - sum1);
    }
}

 

---

다. 참고

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

// 백준 17471 게리맨더링
//O(N*2의N승) N => 10

// 반례
//3
//1 2 3
//1 2
//1 1
//0
public class Main_17471_게리맨더링 {
    static int N;
    static int[] peoples;
    static int[][] maps;
    static int result = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        peoples = new int[N+1];
        int[] teams = new int[N+1];
//        각 구역별 인원 입력받기
        for(int i = 1; i <= N; i++) {
            peoples[i] = sc.nextInt();            
        }        
//        구역별 연결된 정보 입력 받기
        maps = new int[N+1][N+1];
        int cnt = 0;
        for(int i = 1;i <= N; i++) {
            cnt = sc.nextInt();
            int idx;
            for(int c = 0; c < cnt; c++) {
                 idx = sc.nextInt();
                 maps[i][idx] = 1;
            }
        }
        sc.close();
        solve(teams, 1);
        if(result == Integer.MAX_VALUE) {
            System.out.println(-1);
        }else {
            System.out.println(result);
        }
    }
    static void solve(int[] teams, int cnt) {
//        모든 지역 배치해보기
        if(cnt == N + 1) {
//            두 구역으로 정확하게 분리되었나 확인하기
//            System.out.println(Arrays.toString(teams));
            if(checkbfs(teams,0) && checkbfs(teams,1)) {
                result = Math.min(result, doCount(teams));
            }
            return;
        }
        teams[cnt] = 0;
        solve(teams, cnt + 1);
        teams[cnt] = 1;
        solve(teams, cnt + 1);

    }    
    static boolean checkbfs(int[] teams, int type) {
        boolean[] v = new boolean[N+1];
        Queue<Integer> q = new LinkedList<Integer>();

//        시작하는 정점을 찾아서 큐에 삽입한다.
        for(int i = 1; i <= N; i++) {
            if(teams[i] == type) {
                q.offer(i);
                v[i] = true;
                break;
            }
        }
//        두 구역으로 분리될 수 없으면 바로 반환
        if(q.isEmpty()) {
            return false;
        }
//        그 정점으로 모두 연결되어 있는지 BFS 검색
        int cur;
        while(!q.isEmpty()) {
            cur = q.poll();
            for(int i = 1; i <= N; i++) {
//                이미 방문한 정점 무시
                if(v[i]) {
                    continue;
                }
//                같은 구역이 아니면 무시
                if(teams[i] != type) {
                    continue;
                }
//                연결되어 있지 않으면 무시
                if(maps[cur][i] == 0) {
                    continue;
                }
//                그렇지 않으면 큐에 삽입하고 방문 체크를 한다.
                q.offer(i);
                v[i] = true;
            }
        }
//        모든 정점을 방문해 보면서 다른 구역은 무시하고 같은 구역이면 방문했는지 체크해서  
//        방문 체크되어 있지 않으면 연결되어 있지 않음으로 바로 false 값을 반환
        for(int i = 1; i <= N; i++) {
            if(teams[i] != type) {
                continue;
            }
            if( !v[i] ) {
                return false;
            }
        }
//        최종까지 오면 모든 구역이 하나로 연결되어 있음
        return true;
    }
    static int doCount(int[] teams) {
        int sum1 = 0;
        int sum2 = 0;
        for(int i = 1; i <= N; i++) {
            if(teams[i] == 0) {
                sum1 += peoples[i];
            }else {
                sum2 += peoples[i];
            }
        }
        return Math.abs(sum1 - sum2);
    }
}

강사님 코드.

 

---