✨ 문제

백준 17471 게리맨더링

🎈 접근 방식

1. N개의 구역을 2개의 선거구로 나누기 위해 이 과정에서 부분집합을 사용한다.
2. 2개의 선거구가 나왔다면 두 선거구 모두 각 구역이 연결되어 있는지를 확인한다
3. 만약 두 선거구 모두 연결되어 있다면 구역별 인구를 더한 후, 차이를 계산해서 최솟값으로 정답을 구한다.

여기서 좀 더 구체화하면 부분집합을 사용해서 선거구 A, B를 나눴는데 최소한 한 구역은 갖고 있어야 하기 때문에 한 쪽의 선거구에 아무것도 없다면 그건 리턴시키도록
연결되어 있는지 확인하기 위해서는 BFS를 사용하기로 했다.
연결되어있는지 확인을 하기 위함이기 때문에 A선거구에서 맨 앞의 구역을 가져와서 BFS를 돌려보고 모두 visited가 되었는지 확인하는 방식으로 했다!

😫 실수한 점이나 놓친 점

이전에도 그랬었는데 groupA, groupB는 부분집합이 만들어질 때 마다 초기화를 해줘야 하는데 맨 처음에 그냥 초기화하고 사용했더니 답이 안나와서 출력을 찍어보니 sumA, sumB가 엄청 커졌다... -> 초기화 하는거 항상 신경써주기!!!
그리고 check함수안에서 while문을 돌리는 과정에서 foreach문을 사용했는데 이때 list에서 꺼낸 i값이 group에 포함되어 있는지에 대한 여부를 확인안해줘서 틀림!
생각해보니 이걸 안해주면 queue에 다른 구역도 들어가버리는거 같다..

💻 풀이 코드

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

/*
 * bfs로 풀면 좀 더 시간이 빠를거같음!! 
 */
public class Main {
	static int n, ans;
	static int[] num; // 각 구역의 인구 수
	static boolean[] selected; // 부분집합을 만들기 위해 사용
	static boolean[] visited; // 나중에 연결되었는지 확인하기 위해 bfs로 할 때 사용
	static List<Integer> groupA; // a 선거구
	static List<Integer> groupB; // b 선거구
	static List<List<Integer>> list = new ArrayList<>(); // 각 구역별 인구 수

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine()); // 지역의 개수
		StringTokenizer st = new StringTokenizer(br.readLine());
		ans = Integer.MAX_VALUE; // 정답으로 쓸 최댓값
		num = new int[n + 1];
		selected = new boolean[n + 1];

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

		for (int i = 0; i <= n; i++) {
			list.add(new ArrayList<>());
		}

		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			int k = Integer.parseInt(st.nextToken());
			for (int j = 0; j < k; j++) {
				list.get(i).add(Integer.parseInt(st.nextToken()));
			}
		}

		subset(0);
		ans = (ans == Integer.MAX_VALUE) ? -1 : ans;
		System.out.println(ans);

	}

	static void subset(int srcIdx) {
		if (srcIdx == n) {
			groupA = new ArrayList<>();
			groupB = new ArrayList<>();

			for (int i = 1; i <= n; i++) {
				if (selected[i]) {
					groupA.add(i);
				} else {
					groupB.add(i);
				}
			}
			// 한 그룹에만 다 몰리면 안되니깐
			if (groupA.size() == 0 || groupB.size() == 0) {
				return;
			}
			if (check(groupA) && check(groupB)) {
				int sumA = 0;
				int sumB = 0;
//				System.out.println("grupA= " +groupA + "groupB= " + groupB);
				// 둘 다 연결되었는지 확인되었다면 인구 수 세어서 ans에 넣어주기 반복
				for (int a : groupA) {
					sumA += num[a];
				}
				for (int b : groupB) {
					sumB += num[b];
				}
//				System.out.println("sumA= " + sumA);
//				System.out.println("sumB= " + sumB);

				ans = Math.min(ans, Math.abs(sumA - sumB));
			}
			return;
		}
		selected[srcIdx] = true;
		subset(srcIdx + 1);
		selected[srcIdx] = false;
		subset(srcIdx + 1);
	}

	static boolean check(List<Integer> group) {
		Queue<Integer> queue = new ArrayDeque<>();
		visited = new boolean[n + 1];
		visited[group.get(0)] = true;
		queue.offer(group.get(0));

		while (!queue.isEmpty()) {
			Integer p = queue.poll();
			for (int i : list.get(p)) {
				if (!visited[i] && group.contains(i)) {
					visited[i] = true;
					queue.offer(i);
				}
			}
		}

		// 전부 다 방문했다면 연결이 되어있다는거고 안된 지점이 있다는건 연결이 안된다는 점!
		for (int g : group) {
			if (!visited[g]) {
				return false;
			}
		}

		return true;
	}

}