[백준] 게리맨더링 - 17471

문제설명

 

www.acmicpc.net/problem/17471

17471번: 게리맨더링

 

 

기본아이디어

주어진 지점들을 두 분류로 나누고, 각 지점들의 값들의 합의 차이 중 최소값을 찾는 문제이다. 여기서 중요한 점은 두 분류로 나눴을 때 각각의 점들이 다 이어져 있어야 합니다.

 

주어지는 N값이 작기 때문에 dfs, bfs 탐색으로 해도 된다는 생각이 들었고, 그래서 조합으로 가능한 경우를 다 만든 다음에 bfs탐색으로 연결이 되어있는지 확인하는 방법을 사용했습니다.

 

PS. 너무 많이 틀려서 반례를 많이 찾아봤는데 여기서 많이 도움이 됐습니다.www.acmicpc.net/board/view/54133

글 읽기 - C#) 어디서 틀렸는지 감이 안잡힙니다. + 시도해 본 케이스들

 

구현코드

public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));
        N = Integer.parseInt(input.readLine());
        population = new int[N+1];
        StringTokenizer st = new StringTokenizer(input.readLine());
        total_sum = 0;
        for(int i = 1; i <= N; i++) {
            population[i] = Integer.parseInt(st.nextToken());
            total_sum += population[i];
        }
        map = new ArrayList[N+1];
        for(int i = 1; i <= N; i++)
            map[i] = new ArrayList<Integer>();
        for(int i = 1; i <= N; i++){
            st = new StringTokenizer(input.readLine());
            int cnt = Integer.parseInt(st.nextToken());
            for(int j= 0; j < cnt; j++)
                map[i].add(Integer.parseInt(st.nextToken()));
        }
        visited = new boolean[N+1];
        min = Integer.MAX_VALUE;
        dfs(1,0, 0);
 
 
        System.out.println(min==Integer.MAX_VALUE?-1:min);
    }
    static int N;
    static int[] population;
    static List<Integer>[] map;
    static int min, total_sum;
    static boolean[] visited;
    static void dfs(int idx, int cnt, int sum){
        if(chk1() && chk2()) {
            int diff = Math.abs(total_sum - sum * 2);
            if (diff < min) {
                min = diff;
            }
        }else if(cnt == N)
            return;
 
        for(int i = idx; i <= N; i++){
            if(!visited[i]){
                visited[i] = true;
                dfs(i+1, cnt+1, sum + population[i]);
                visited[i] = false;
            }
        }
    }
 
    static boolean chk1(){
        int start = 0;
        boolean[] chkArr = new boolean[N+1];
        for(int i = 1; i <= N; i++){
            if(!visited[i]) {
                chkArr[i] = true;
                start = i;
            }
        }
        if(start == 0)
            return false;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        while(!queue.isEmpty()){
            int temp = queue.poll();
            chkArr[temp] = false;
            for(int next: map[temp]){
                if(chkArr[next]){
                    queue.add(next);
                }
            }
        }
        for(boolean ok : chkArr){
            if(ok)
                return false;
        }
        return true;
    }
 
    static boolean chk2(){
        int start = 0;
        boolean[] chkArr = new boolean[N+1];
        for(int i = 1; i <= N; i++){
            if(visited[i]) {
                chkArr[i] = true;
                start = i;
            }
        }
        if(start == 0)
            return false;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        while(!queue.isEmpty()){
            int temp = queue.poll();
            chkArr[temp] = false;
            for(int next: map[temp]){
                if(chkArr[next]){
                    queue.add(next);
                }
            }
        }
        for(boolean ok : chkArr){
            if(ok)
                return false;
        }
        return true;
    }
 

 

정리, 기억할 내용

1. 처음 아이디어에서 dfs, bfs 어떤걸 사용할지 잘 정하자.

2. 백준에서 질문검색에서 반례 잘 찾아보자.