오늘 풀어볼 문제는 ⭐게리맨더링 이다!
1. 문제 요약
- 2개의 구역으로 나누고, 가장 최소의 인구차를 구하라
- 구역 간 인접한 구역은 0개일 수도 있음 (즉 분리 가능)
- 모든 구역은 선거구에 포함되어야 함.
- 같은 선거구에 있다면, 모두 연결되어 있어야 함.
- 두 선거구로 나눌 수 없는 경우 -1 출력
-> 구역이 3개 이상으로 떨어진 경우
2. 문제 접근법
처음에는 다음과 같이 로직을 구성했다.
[ 풀이법 ]
모든 구역이 이어져있다면, 전체의 인구수에서 한 구역씩 빼면서 최소의 구역 찾기
둘로 나뉘어져 있다면, a집합-b집합
셋 이상으로 나뉘어져 있다면 -1 출력
그리고 이 로직을 그대로 따르는 코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N;
static int people[];
static List<Integer>[] graph;
static int answer = Integer.MAX_VALUE;
static int total = 0;
static boolean [] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
people = new int[N+1];
graph = new List[N+1];
visited = new boolean[N+1];
st = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++) {
people[i] = Integer.parseInt(st.nextToken());
total+=people[i];
graph[i] = new ArrayList<>();
}
for(int i=1; i<=N; i++) {
st = new StringTokenizer(br.readLine());
int nextCount = Integer.parseInt(st.nextToken());
if(nextCount==0) continue;
for(int j=0; j<nextCount; j++) {
int next = Integer.parseInt(st.nextToken());
graph[i].add(next);
}
}
//현재 몇 구역으로 구성되어 있는지 찾기
int set = 0;
List<Integer> setStartIndex = new ArrayList<>();
for(int i=1; i<=N; i++){
if(visited[i]) continue;
setStartIndex.add(i);
set++;
findSet(i);
}
if(set==1){
Arrays.fill(visited, false);
findArea(1, people[1], total-people[1]);
System.out.println(answer);
} else if (set==2) {
Arrays.fill(visited, false);
int a = findSetSub(setStartIndex.get(0));
Arrays.fill(visited, false);
int b = findSetSub(setStartIndex.get(1));
System.out.println(Math.abs(a-b));
} else {
System.out.println(-1);
}
}
static void findSet(int now) {
visited[now]=true;
for(int i=0; i<graph[now].size(); i++){
int next = graph[now].get(i);
if(visited[next]) continue;
visited[next]=true;
findSet(next);
}
}
static int findSetSub(int now) {
visited[now]=true;
int answer = people[now];
for(int i=0; i<graph[now].size(); i++) {
int next = graph[now].get(i);
if(visited[next]) continue;
answer += findSetSub(next);
}
return answer;
}
static void findArea(int now, int sum, int total) {
if(sum>=total) {
answer = Math.min(answer, sum-total);
return;
}
visited[now]=true;
for(int i=0; i<graph[now].size(); i++){
int next = graph[now].get(i);
if(visited[next]) continue;
findArea(next, sum+people[next], total-people[next]);
}
visited[now]=false;
}
}총 2가지 문제가 있었던 코드이다.
2.1 내 코드 문제점(1)
일단 해당 코드는 다음과 같은 에러를 뱉는다.
Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
이게 왜 때문에 생기는 문제냐, 바로 제네릭 배열 생성 시, 타입이 명확하지 않기 때문이라고 한다.
바로 아래 코드 때문에 발생한 일이다.
List<Integer>[] graph = new List[N+1];테스트에서만 경고를 날릴 뿐, 실제 코드 측정에는 영향을 주지 않았다.
2.2 내 코드 문제점(2)
2번째 문제점은, 당연하게도 그냥 틀린 코드였다. 해당 코드는 1%에서 틀리게 된다.
왜 그럴까?
반례를 보자
test #3 : 1~5번 구역은 1자로 연결됨. 3번 노드에 6번 노드가 붙어있음
6
3 3 3 3 3 3
1 2
2 1 3
3 2 4 6
2 3 5
1 4
1 3
ans : 6
내코드 : 0
해당 그래프는 다음과 같이 그려져있다.
1 - 2 - 3 - 4 - 5
|
6현재 내 코드는 모든 노드가 이어져있다고 가정한다면 무조건 1번 노드 vs 나머지 노드 로 구역을 나눈다.
그리고 나서 현재 노드(첫 번째 순서일 경우 1번 노드)와 붙어있는 노드를 차근차근 1번 노드 구역으로 넘기면서 그 차를 조사하고 있다.
그래서 다음과 같은 {1, 2, 3} vs {4, 5, 6} 구역으로 나뉜 케이스를 잡아내지 못하고 틀려버리는 것이다!!!
3. 정답 코드
GGGGG 형님의 코드이다.
접근법은 다음과 같다.
[풀이법]
: 모든 선거구 조합을 탐색
- 각 구역을 A 선거구 또는 B 선거구로 나누는 모든 경우의 수(부분 집합) 생성
- 두 개의 선거구로 나눌 수 있는지 확인
- 한쪽 선거구가 비어 있다면 무효
- 각 선거구가 연결된 그래프인지 검사
- 유효한 경우 인구 차이 계산
- 두 선거구의 총 인구 차이를 구하고 최소값 갱신
- 모든 가능한 경우를 탐색한 후 최소 인구 차이 출력
- 최소값 갱신이 안된 경우 -1 출력
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int[] people;
static List<Integer>[] graph;
static boolean[] selected;
static int total = 0, answer = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
people = new int[N + 1];
graph = new ArrayList[N + 1];
selected = new boolean[N + 1];
for (int i = 1; i <= N; i++) {
graph[i] = new ArrayList<>();
}
// 인구 정보 입력
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
people[i] = Integer.parseInt(st.nextToken());
total += people[i];
}
// 그래프 연결 정보 입력
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
int nextCount = Integer.parseInt(st.nextToken());
for (int j = 0; j < nextCount; j++) {
int next = Integer.parseInt(st.nextToken());
graph[i].add(next);
graph[next].add(i); // ✅ 양방향 연결 추가
}
}
// ✅ 모든 선거구 조합 탐색
subset(1);
// 정답 출력
System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
}
// ✅ 부분 집합을 만들어 모든 선거구 조합 탐색
static void subset(int idx) {
if (idx == N + 1) {
checkValidDivision(); // 두 개의 선거구로 나눌 수 있는지 확인
return;
}
// 현재 구역을 선거구 A에 포함
selected[idx] = true;
subset(idx + 1);
// 현재 구역을 선거구 B에 포함
selected[idx] = false;
subset(idx + 1);
}
// ✅ 두 개의 선거구로 나눌 수 있는지 확인
static void checkValidDivision() {
List<Integer> areaA = new ArrayList<>();
List<Integer> areaB = new ArrayList<>();
for (int i = 1; i <= N; i++) {
if (selected[i]) areaA.add(i);
else areaB.add(i);
}
// 한쪽 선거구가 비어 있다면 잘못된 분할
if (areaA.isEmpty() || areaB.isEmpty()) return;
// 두 선거구가 각각 연결 그래프인지 확인
if (isConnected(areaA) && isConnected(areaB)) {
int sumA = 0, sumB = 0;
for (int i : areaA) sumA += people[i];
for (int i : areaB) sumB += people[i];
answer = Math.min(answer, Math.abs(sumA - sumB));
}
}
// ✅ BFS로 연결된 선거구인지 확인
static boolean isConnected(List<Integer> area) {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[N + 1];
queue.offer(area.get(0)); // 첫 번째 지역에서 탐색 시작
visited[area.get(0)] = true;
int count = 1;
while (!queue.isEmpty()) {
int current = queue.poll();
for (int next : graph[current]) {
if (!visited[next] && area.contains(next)) {
queue.offer(next);
visited[next] = true;
count++;
}
}
}
// 모든 노드를 방문했으면 true, 그렇지 않으면 false
return count == area.size();
}
}
3.1 핵심 함수 - subset(int idx)
해당 함수는 모든 경우의 수에 대한 조합을 만드는 함수이다!!
처음엔 모든 노드들이 true의 값을 가지다가, 점차 false를 가지며 모든 경우의 수를 탐색할 수 있게 될 것이다.
그리고 모든 노드들의 집합이 정해졌을 때 (idx==N+1), 두 개의 선거구로 나눌 수 있는지 확인하는 함수를 호출한다.
// ✅ 부분 집합을 만들어 모든 선거구 조합 탐색
static void subset(int idx) {
if (idx == N + 1) {
checkValidDivision(); // 두 개의 선거구로 나눌 수 있는지 확인
return;
}
// 현재 구역을 선거구 A에 포함
selected[idx] = true;
subset(idx + 1);
// 현재 구역을 선거구 B에 포함
selected[idx] = false;
subset(idx + 1);
}3.2 핵심 함수 - checkValidDivision()
2개의 연결리스트를 만들고, subset함수에서 정한 구역별로 리스트에 담아준다.
그리고 각 리스트의 원소들이 모두 이어져있는지 확인하는 isConnected함수를 호출한다.
( 만약 두 리스트 중 하나라도 비어있다면, 다른 한쪽의 리스트에 모든 노드가 쏠려 2개의 집단이 되지 못한다는 이야기이니 이때는 바로 return 해준다. )
// ✅ 두 개의 선거구로 나눌 수 있는지 확인
static void checkValidDivision() {
List<Integer> areaA = new ArrayList<>();
List<Integer> areaB = new ArrayList<>();
for (int i = 1; i <= N; i++) {
if (selected[i]) areaA.add(i);
else areaB.add(i);
}
// 한쪽 선거구가 비어 있다면 잘못된 분할
if (areaA.isEmpty() || areaB.isEmpty()) return;
// 두 선거구가 각각 연결 그래프인지 확인
if (isConnected(areaA) && isConnected(areaB)) {
int sumA = 0, sumB = 0;
for (int i : areaA) sumA += people[i];
for (int i : areaB) sumB += people[i];
answer = Math.min(answer, Math.abs(sumA - sumB));
}
}3.2 핵심 함수 - isConnected()
가장 쉬운 함수이다! 바로 bfs로 인자로 받아온 리스트들이 모두 이어져있는지 확인해주는 코드이다.
해당 함수에서 모든 리스트가 연결되어 있다면 true를, 그렇지 않다면 false를 반환하게 된다.
그 후 다시 checkValidDivision() 함수로 돌아가서, 두 집단 모두 true 반환 시 최소값을 갱신해주며 흘러가게 되는 코드였다!
// ✅ BFS로 연결된 선거구인지 확인
static boolean isConnected(List<Integer> area) {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[N + 1];
queue.offer(area.get(0)); // 첫 번째 지역에서 탐색 시작
visited[area.get(0)] = true;
int count = 1;
while (!queue.isEmpty()) {
int current = queue.poll();
for (int next : graph[current]) {
if (!visited[next] && area.contains(next)) {
queue.offer(next);
visited[next] = true;
count++;
}
}
}
// 모든 노드를 방문했으면 true, 그렇지 않으면 false
return count == area.size();
}4. 느낀점
답을 보니 너무 쉬웠다. 하지만 난 너무너무 어렵다고 생각했었는데 문제 많이 안풀 이슈로 subset함수처럼 조합을 만드는 방법을 생각해내지 못했던 것 같다. 당시 문제풀 때도 이부분이 가장 힘들었었다.
위 코드처럼 조합을 만들고 로직을 짜내려가는 걸 이해하니 너무 재밌었다. 다음에 이런 조합 문제를 좀 더 많이 풀어봐야겠다고 생각했다.
끝!
