[백준] 17471 게리맨더링 - Brute Force / Java

• 문제 링크

17471번: 게리맨더링

 

• 풀이 과정

각 구역의 번호를 인덱스로 지정하는 value 배열에 인구 값을 입력받고,

인접행렬에 각 구역과 인접한 구역의 정보를 입력받아 인접할 시 1로 저장한다.

 

구역을 둘로 나누기 위해 한 구역은 subset 배열의 true, 다른 한 구역은 false 로 나타내며,

재귀 함수(recur) 를 통해 구역을 둘로 나누는 모든 경우의 수를 각 구역의 값의 합을 누적하며 구한다.

 

경우의 수가 구해지면, 매개변수를 true 또는 false 로 전달받는 isConnected 함수로

해당 경우의 두 구역이 문제에 조건에 부합하는 지 검사한다.

 

먼저 검사하는 구역에 포함하는 시작점을 찾고,(subset[i] == flag)

같은 구역에 속하며, 구역끼리 인접하고 방문하지 않은 구역

(subset[i] == flag && map[node][i] == 1 && !visit[i]) 을 탐색해나가며 이동 가능한 구역을 방문 처리한다.

 

이 후 같은 구역에 속하지만 방문한 적이 없는, 즉 연결되지 않는 구역이 존재한다면 false 를 반환,

이 조건까지 통과할 경우 true 를 반환한다.

 

이렇게 두 구역이 문제의 조건에 맞게 나뉘어 졌다면, 두 구역의 인구차의 최솟값을 갱신한다.

 

만약 최솟값이 갱신되었다면 해당 값을, 아니면 -1 을 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int n, total;
    static int[] value;
    static int[][] map;
    static boolean[] subset;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        value = new int[n + 1];
        map = new int[n + 1][n + 1];
        subset = new boolean[n + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            value[i] = Integer.parseInt(st.nextToken());
            total += value[i];
        }

        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            for (int j = 0; j < m; j++)
                map[i][Integer.parseInt(st.nextToken())] = 1;
        }

        recur(1, 0);

        bw.write((min == Integer.MAX_VALUE ? -1 : min) + "\n");
        bw.flush();
    }

    private static void recur(int idx, int sum) {
        if (idx > n) {
            if (isConnected(true) && isConnected(false))
                min = Math.min(min, Math.abs(sum - (total - sum)));

            return;
        }

        subset[idx] = true;
        recur(idx + 1, sum + value[idx]);
        subset[idx] = false;
        recur(idx + 1, sum);
    }

    private static boolean isConnected(boolean flag) {
        Queue<Integer> q = new LinkedList<>();
        boolean[] visit = new boolean[n + 1];

        for (int i = 1; i <= n; i++) {
            if (subset[i] == flag) {
                q.offer(i);
                visit[i] = true;
                break;
            }
        }

        while (!q.isEmpty()) {
            int node = q.poll();
            for (int i = 1; i <= n; i++) {
                if (subset[i] == flag && map[node][i] == 1 && !visit[i]) {
                    q.offer(i);
                    visit[i] = true;
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            if (subset[i] == flag && !visit[i])
                return false;
        }

        return true;
    }

}