[백준 17471] 게리맨더링 (JAVA)

🔰 문제

---

백준 17471번: 게리맨더링 (Gold 4)

💡 접근방식

---

1. 1~N까지 구역을 2개의 선거구로 나눠주기 (부분집합)
2. 나눠준 선거구 내에서 구역들이 전부 연결되었는지 확인 (그래프 탐색 - BFS)
3. 전부 연결되어 있으면 인구차 구하기

2개의 선거구로 나눠주는 것은 부분집합 구할 때 처럼 구할 수 있다.

나눠준 선거구 내에서 구역들이 전부 연결되었는지는 A선거구에 속하는 지역 하나를 뽑아서 그래프 탐색을 실시, B 선거구에 속하는 지역 하나를 뽑아서 그래프 탐색을 실시 후 각 그래프 탐색의 방문 결과가 선거구 분리 결과와 같은지 비교한다.

선거구 내의 지역들이 전부 연결되었으면, 각 선거구 별 인구차를 나눠준다.

💦 풀면서 실수, 놓친 점

---

boolean selected[] 배열을 만들어 A 선거구일 땐 true값을 저장하고, B선거구일 땐 false를 저장하게 하였다.
접근 방식에서 언급한 1번(선거구 나눠주기), 3번(선거구 인구차 구하기) 에선 문제가 없었지만 2번 문제를 풀 때 헷갈렸다.

차라리 헷갈리지 않기 위해 선거구 나누기가 끝나고 selected 결과에 따라 ArrayList<Integer> aList, bList를 만들어서 A, B 선거구에 해당하는 지역 번호를 저장해주는 것이 훨씬 더 실수하지 않을 것 같다.

🕑 소요시간

40분

💻 풀이

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

public class Main_17471_2 {

	static int N;
	static int peoples[]; // 구역별 인구수
	static List<ArrayList<Integer>> graph;
	static boolean selected[];
	static boolean visited[];
	static int res;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine()); // 지역 개수
		res = Integer.MAX_VALUE; // 인구 차이(정답)
		peoples = new int[N]; // 지역별 인구 수
		selected = new boolean[N]; // 부분집합 만들 때 사용

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) // 지역별 인구 수 입력
			peoples[i] = Integer.parseInt(st.nextToken());

		graph = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			graph.add(new ArrayList<Integer>());
		}

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int cnt = Integer.parseInt(st.nextToken()); // 인접 구역 수
			for (int j = 0; j < cnt; j++) {
				int num = Integer.parseInt(st.nextToken());
				graph.get(i).add(num - 1);
			}
		}

		divide(0);
		if (res == Integer.MAX_VALUE)
			res = -1;
		System.out.println(res);

	}

	private static void divide(int idx) { // 1. 선거구 나누기
		if (idx == N) {
			List<Integer> aList = new ArrayList<>();
			List<Integer> bList = new ArrayList<>();
			for (int i = 0; i < N; i++) {
				if (selected[i])
					aList.add(i);
				else
					bList.add(i);
			}
			if (aList.size() == 0 || bList.size() == 0) // 한 지역에 몰빵 X
				return;
			
			if (check(aList) && check(bList)) { // 두 구역이 각각 연결되었는지 확인
				getPeopleDiff(); // 인구차 구하기
			}
			return;
		}

		selected[idx] = true;
		divide(idx + 1);
		selected[idx] = false;
		divide(idx + 1);

	}

	private static boolean check(List<Integer> list) {

		Queue<Integer> q = new LinkedList<>();
		visited = new boolean[N];
		visited[list.get(0)] = true;
		q.offer(list.get(0));
		
		int count = 1; // 방문한 지역 개수
		while (!q.isEmpty()) {
			int cur = q.poll();
			for (int i = 0; i < graph.get(cur).size(); i++) {
				int y = graph.get(cur).get(i);
				if(list.contains(y) && !visited[y]) { // 선거구에 해당하고, 아직 미방문
					q.offer(y);
					visited[y] = true;
					count ++;
				}
			}
		}
		if(count==list.size()) // 선거구에 해당하는 지역수와 방문한 지역수가 같은 경우
			return true;
		else
			return false;
	}


	private static void getPeopleDiff() { // 3. 선거구의 인구 차 구하기
		// a구역 사람수
		int pA = 0, pB = 0;
		for (int i = 0; i < N; i++) {
			if (selected[i])
				pA += peoples[i];
			else
				pB += peoples[i];
		}
		int diff = Math.abs(pA - pB);
		res = Math.min(res, diff);
	}

}

🌟 비슷한 유형의 문제들

---

참고