백준 17471 (게리맨더링) - java

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

17471번: 게리맨더링

문제 : 게리맨더링 (17471)

유형 : 조합론 + BFS

 

접근

• 선거구를 2개의 영억으로 나눈다. (조합론 사용)
• 각 선거구에 대하여 BFS를 수행한다. (2개의 영역에 대해서 총 BFS 2번 수행)
• 방문하지 못한 도시가 있다면 -1
• 모든 도시를 방문했다면 각 영역의 인구수의 차이를 구한다.
  • 최솟값을 구한다 !

조합론

• 조합론에 대한 구현은 백트랙킹을 사용하였다.

코드

    static void go(int start,int r,int b)
    {
        if(r>=n || b >=n)
            return; // 한 영역이 모든 점을 포함할 수 없다 !

        if(r+b == n) // 모든 영역의 배분이 완료되었다면
        {
            int tmp = search(); // 차이를 구한다.
            if(tmp != -1)
                result = Math.min(result,tmp); // 최솟값 갱신
            return;
        }

        for(int i=start;i<=n;i++)
        {
            if(!visit[i])
            {
                visit[i] = true;
                color[i] = 1; // 1의 영역
                go(i+1,r+1,b);
                color[i] = 2; // 2의 영역
                go(i+1,r,b+1);
                color[i] = 0;
                visit[i] = false;
            }
        }
    }

탐색 : BFS 사용

• 1의 영역 , 2의 영역 2개에 대하여 2번의 BFS를 수행해야 한다.

코드

    static int search()
    {
        Queue<Integer> qr = new LinkedList<>();
        Queue<Integer> qb = new LinkedList<>();

        boolean[] v = new boolean[n+1];

        int rsum = 0;
        int bsum = 0;
        for(int i=1;i<=n;i++)
        {
            if(color[i] == 1)
            {
                qr.add(i); // 1의 영역 지점중 한개만 추출
                v[i] = true;
                rsum += num[i];
                break;
            }
        }

        for(int i=1;i<=n;i++)
        {
            if(color[i] == 2)
            {
                qb.add(i); // 2의 영역 지점중 한개만 추출
                v[i] = true;
                bsum += num[i];
                break;
            }
        }
		// 1의 영역에 대한 BFS
        while(!qr.isEmpty())
        {
            Integer cur = qr.poll();

            for(int next : graph[cur])
            {
                if(!v[next] && color[next] == 1)
                {
                    v[next] = true;
                    rsum += num[next];
                    qr.add(next);
                }
            }
        }
		// 2의 영역에 대한 BFS
        while(!qb.isEmpty())
        {
            Integer cur = qb.poll();

            if(!v[cur])
            {
                v[cur] = true;
                bsum += num[cur];
            }

            for(int next : graph[cur])
            {
                if(!v[next] && color[next] == 2)
                {
                    v[next] = true;
                    bsum += num[next];
                    qb.add(next);
                }
            }
        }

        for(int i=1;i<=n;i++)
        {
            if(!v[i])
            {
                return -1; // 방문하지 못한 지점이 있다면 잘못된 분할인 것이다 !
            }
        }

        return Math.abs(rsum - bsum); // 차이를 반환
    }

전체 코드

import java.util.*;
import java.io.*;

public class Main {
    static int n = 0;
    static int[] num;

    static ArrayList<Integer>[] graph;

    static boolean[] visit;

    static int[] color;

    static int result = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        num = new int[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=1;i<=n;i++)
        {
            num[i] = Integer.parseInt(st.nextToken());
        }

        graph = new ArrayList[n+1];
        visit = new boolean[n+1];
        color = new int[n+1];
        for(int i=1;i<=n;i++)
        {
            graph[i] = new ArrayList<>();
            st = new StringTokenizer(br.readLine()," ");
            int num = Integer.parseInt(st.nextToken());

            for(int j=1;j<=num;j++)
            {
                graph[i].add(Integer.parseInt(st.nextToken()));
            }
        }

        go(1,0,0);

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

    static void go(int start,int r,int b)
    {
        if(r>=n || b >=n)
            return;

        if(r+b == n)
        {
            int tmp = search();
            if(tmp != -1)
                result = Math.min(result,tmp);
            return;
        }

        for(int i=start;i<=n;i++)
        {
            if(!visit[i])
            {
                visit[i] = true;
                color[i] = 1;
                go(i+1,r+1,b);
                color[i] = 2;
                go(i+1,r,b+1);
                color[i] = 0;
                visit[i] = false;
            }
        }
    }

    static void printColor() {
        for (int i = 1; i <= n; i++) {
            System.out.print(color[i] + " ");
        }
        System.out.println();
    }

    static int search()
    {
        Queue<Integer> qr = new LinkedList<>();
        Queue<Integer> qb = new LinkedList<>();

        boolean[] v = new boolean[n+1];

        int rsum = 0;
        int bsum = 0;
        for(int i=1;i<=n;i++)
        {
            if(color[i] == 1)
            {
                qr.add(i);
                v[i] = true;
                rsum += num[i];
                break;
            }
        }

        for(int i=1;i<=n;i++)
        {
            if(color[i] == 2)
            {
                qb.add(i);
                v[i] = true;
                bsum += num[i];
                break;
            }
        }

        while(!qr.isEmpty())
        {
            Integer cur = qr.poll();

            for(int next : graph[cur])
            {
                if(!v[next] && color[next] == 1)
                {
                    v[next] = true;
                    rsum += num[next];
                    qr.add(next);
                }
            }
        }

        while(!qb.isEmpty())
        {
            Integer cur = qb.poll();

            if(!v[cur])
            {
                v[cur] = true;
                bsum += num[cur];
            }

            for(int next : graph[cur])
            {
                if(!v[next] && color[next] == 2)
                {
                    v[next] = true;
                    bsum += num[next];
                    qb.add(next);
                }
            }
        }

        for(int i=1;i<=n;i++)
        {
            if(!v[i])
            {
                return -1;
            }
        }

        return Math.abs(rsum - bsum);
    }

}