링크

17471 게리맨더링

문제

풀이

처음에 문제를 이해를 못해서 시간이 오래걸렸다.

예제 그림을 보면서 입력을 살펴보자
일단 첫번째줄 6은 6줄까지 그래프를 표현한다 라고 생각하면 된다.
두번째줄은 인구수를 설명하고 있다.
세번째줄부터 아래로 6줄은 그래프를 표현한다.

• 세번째 줄 2 2 4 는 첫번째 2는 1번 노드가 2개의 노드와 연결되어 있다는 것을 암시하고 그것이 2와 4라는 뜻이다.
• 네번째 줄도 보자면 4 1 3 6 5로 구성되어 있고 첫번째 4는 2번 노드가 4개의 노드와 연결되어 있고 그 노드들은 각각 1 3 6 5라는 말이다.

이걸 이해 못해서 한참 헤맸다.

나의 풀이

• 일단 저 입력들을 2차원 배열에 표시했다.(연결되어 있으면 1로 표현)
• 조합을 통해 모든 경우의 수를 만든다.
• 위에서 만들어진 경우의 수를 하나하나 bfs 돌려서 딱 2덩이로 갈라져있는지 체크
• 2덩이라면 인구수 차이를 구해서 작은 값을 저장한다.
• 만약 모든 경우의 수를 bfs 돌렸는데 2덩이가 없다면 -1을 출력하도록 한다.

코드

import java.awt.desktop.PreferencesEvent;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    public static List<Integer> list = new ArrayList<>();
    public static boolean[] visited;
    public static int count = 0;
    public static int[][] map;
    public static String[] people;
    public static int min = -1;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        people = br.readLine().split(" ");

        map = new int[n+1][n+1];

        for(int i=1;i<=n;i++){
            String[] arr = br.readLine().split(" ");
            int k = Integer.parseInt(arr[0]);

            for(int j=1;j<=k;j++){
                map[i][Integer.parseInt(arr[j])] = 1;
                map[Integer.parseInt(arr[j])][i] = 1;
            }

        }

//        for(int i=0;i<map.length;i++) System.out.println(Arrays.toString(map[i]));

//        System.out.println("--------------");
        visited = new boolean[n+1];
        dfs(visited.length, 0);
        System.out.println(min);

    }

    public static void dfs(int number, int lastIdx){
        if(list.size() == number-2){
//            System.out.println(list);
            return;
        }

        for(int i=1;i<number;i++){
            if(!visited[i] && i >= lastIdx){
                visited[i] = true;
                list.add(i);
                if(bfs(number) == 2){
                    if(min == -1) min = Integer.MAX_VALUE;
                    int left = 0;
                    int right = 0;

                    for(int j=1;j<number;j++){
                        if(list.contains(j)){
                            left += Integer.parseInt(people[j-1]);
                        } else{
                            right += Integer.parseInt(people[j-1]);
                        }
                    }
//                    System.out.println("left = " + left);
//                    System.out.println("right = " + right);
//
//                    System.out.println("list = " + list);
//                    if(min > Math.abs(left - right)){
                        min = Math.min(min, Math.abs(left - right));
//                    }
//                    System.out.println("min = " + min);

                };
                dfs(number, i);
                list.remove(list.size() - 1);
                visited[i] = false;
            }
        }
    }

    public static int bfs(int size){
        count = 0;
        boolean[] link = new boolean[size];
        boolean[] linkVisited = new boolean[size];
        for(int i=0;i<list.size();i++){
            int idx = list.get(i);

            link[idx] = true;
        }
//        System.out.println("list = " + list);
//        System.out.println("link = " + Arrays.toString(link));
        for(int i=1;i<size;i++){
            if(!linkVisited[i]){
                Queue<Integer> queue = new LinkedList<>();
                queue.add(i);
                boolean isColor = link[i];
                linkVisited[i] = true;
                count++;

                while(!queue.isEmpty()){
                    int x = queue.poll();
//                    System.out.println("poll = " + x);
                    for(int j=1;j<size;j++){
                        if(map[x][j] == 1 && link[j] == isColor && !linkVisited[j]){
//                            System.out.println("j번째 인덱스 = " + j);
                            linkVisited[j] = true;
                            queue.add(j);
                        }
                    }
                }

//                System.out.println(Arrays.toString(linkVisited));

            }
        }


        return count;
    }


}