(17471) 게리맨더링
생성일: 2023년 10월 12일 오전 9:34
문제 🌐
백준시의 시장 최백준은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 최백준은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 백준시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.
백준시는 N개의 구역으로 나누어져 있고, 구역은 1번부터 N번까지 번호가 매겨져 있다. 구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.
아래 그림은 6개의 구역이 있는 것이고, 인접한 구역은 선으로 연결되어 있다.
아래는 백준시를 두 선거구로 나눈 4가지 방법이며, 가능한 방법과 불가능한 방법에 대한 예시이다.
공평하게 선거구를 나누기 위해 두 선거구에 포함된 인구의 차이를 최소로 하려고 한다. 백준시의 정보가 주어졌을 때, 인구 차이의 최솟값을 구해보자.
입력
첫째 줄에 구역의 개수 N이 주어진다. 둘째 줄에 구역의 인구가 1번 구역부터 N번 구역까지 순서대로 주어진다. 인구는 공백으로 구분되어져 있다.
셋째 줄부터 N개의 줄에 각 구역과 인접한 구역의 정보가 주어진다. 각 정보의 첫 번째 정수는 그 구역과 인접한 구역의 수이고, 이후 인접한 구역의 번호가 주어진다. 모든 값은 정수로 구분되어져 있다.
구역 A가 구역 B와 인접하면 구역 B도 구역 A와 인접하다. 인접한 구역이 없을 수도 있다.
출력
첫째 줄에 백준시를 두 선거구로 나누었을 때, 두 선거구의 인구 차이의 최솟값을 출력한다. 두 선거구로 나눌 수 없는 경우에는 -1을 출력한다.
제한 사항
- 2 ≤ N ≤ 10
- 1 ≤ 구역의 인구 수 ≤ 100
접근 방법
조합 + 그래프 탐색을 통해 두 구역을 나누는 문제이다. 역량 테스트 준비의 일환으로 풀어보며 저번 시험의 아쉬움을 치료했다….
처음 이 문제를 봤을 때는 생각하는 게 어려웠지만 다시 만났을 때 꽤나 괜찮았다. 나중에 이런 문제를 또 만난다면
- 연결된 구역을 먼저 확인할지
- 조합을 구하고 연결되었는지 확인할지
정하고 시작하는 것이 좋을 것 같다.
- 연결된 지역을 파악하기 위해 인접 리스트를 활용해 지역마다 연결된 지역 번호를 모아 두었다.
N = sc.nextInt();
popul = new int[N + 1];
graph = new ArrayList[N + 1];
chk = new boolean[N+1];
for (int i = 1; i <= N; i++) {
popul[i] = sc.nextInt();
graph[i] = new ArrayList<>();
answer += popul[i];
}
totalP = answer;
for (int i = 1; i <= N; i++) {
int link = sc.nextInt();
for (int idx=0; idx<link; idx++) {
graph[i].add(sc.nextInt());
}
}
조합을 이용해 전체 도시를 두 지역구으로 나눈다. ⇒ 한 가지 조합만 구하고, 두 지역구에 있는 선거구들이 모두 인접해 있는지 확인하기 전에 다른 조합도 구한다. (1, N-1), (2, N-2), (3, N-3), … (N-1, 1) 까지 모든 조합을 구해야 하는데, N/2 개부터는 같은 조합이 나오기 때문에 N/2 개까지만 구했다. 여기서 N이 짝수일 때와 홀수일 때를 구분하지 않아 오류가 발생했다…. 그래서 half라는 변수를 하나 초기화해준다.
int half = 0;
if ( N % 2 == 0) {
half = N/2;
} else {
half = N/2 +1 ;
}
for (int cnt=1; cnt<=half; cnt++) {
int[] comb1 = new int[cnt];
combination(cnt, 0, comb1, 1);
}
if (!answerFlag) System.out.println(-1);
else System.out.println(answer);
조합 구하기
항상 사용하는 그 방법… 을 썼고 조합이 완성되면 그 조합과 다른 조합이 모두 연결되었는지 확인하는 메소드로 넘겨 확인하고, 만약 연결되어 있는 상태라면 조합의 인구수 합을 구한 후 총 인구수에서 뺀 값과 차이를 기존 정답과 비교하여 갱신한다. (최소값을 구해야 하기 때문에 입력받을 때 answer를 전체 인구수로 만들어 뒀다.)
그리고 구역을 나눌 수 있는 조합이 하나도 없는 경우에는 -1을 출력해야 하기 때문에 answerFlag를 가지고 있다가 초기화한다. 구역 나누기가 가능한 조합이 하나라도 나온다면 answerFlag를 true로 변경한다.
static void combination(int cnt, int idx, int[] tempArr, int start) {
if (idx == cnt) {
int[] region1 = Arrays.copyOf(tempArr, cnt);
if(linkChk(region1)) {
answerFlag = true;
int sum1 = 0;
for (int i: region1) {
sum1 += popul[i];
}
// System.out.println("totalP, sum1: "+totalP+" "+sum1);
answer = Math.min(answer, Math.abs((totalP - sum1)-sum1));
}
return;
}
for (int i=start; i<=N; i++) {
if (!chk[i]) {
chk[i] = true;
tempArr[idx] = i;
combination(cnt, idx+1, tempArr, i+1);
chk[i] = false;
}
}
}
연결되었는지 확인하기
bfs를 활용하여 같은 선거구로 분리된 지역이 모두 인접해 있는지 확인한다.
2번 구역을 만들 때 boolean 배열을 이용한 것을 확인하여 true로 바뀐 것은 1번 구역에 속하고, false로 바뀐 것은 2번 구역에 속한다.
따라서 bfs로 확인할 때 인접해 있고, 방문하지 않았을 뿐 아니라 tempChk 배열에서 같은 값을 가지는지 확인한 후 큐에 넣어야 한다.
이렇게 두 구역을 모두 bfs 돌고 난 후에, visited 배열의 1번~N번 인덱스의 값이 true로 변경되어 있어야 한다. 그게 아니라면, 문제의 조건을 만족하지 않기 때문에 false를 리턴한다.
static boolean linkChk(int[] region1) {
boolean[] visited = new boolean[N+1];
boolean[] tempChk = new boolean[N+1];
int[] region2 = new int[N-region1.length];
// System.out.println("확인 전: "+Arrays.toString(visited));
// 두 번째 지역 만들기
int idx = 0;
for (int i: region1) {
tempChk[i] = true;
}
for (int i=1; i<=N; i++) {
if (!tempChk[i]) region2[idx++] = i;
}
// bfs
// 1번 구역 확인
Queue<Integer> q = new LinkedList<>();
q.add(region1[0]);
visited[region1[0]] = true;
while(!q.isEmpty()) {
int curr = q.poll();
for (int i: graph[curr]) {
if (!visited[i] && tempChk[i]) {
q.add(i);
visited[i] = true;
}
}
}
// 2번 구역 확인
q = new LinkedList<>();
q.add(region2[0]);
visited[region2[0]] = true;
while(!q.isEmpty()) {
int curr = q.poll();
for (int i: graph[curr]) {
if (!visited[i] && !tempChk[i]) {
q.add(i);
visited[i] = true;
}
}
}
// System.out.println("region1: "+Arrays.toString(region1));
// System.out.println("region2: "+Arrays.toString(region2));
// System.out.println(Arrays.toString(visited));
// 모두 방문 체크 되어있는지 체크
for (int i=1; i<=N; i++) {
if (!visited[i]) return false;
}
return true;
}
Full Solution
import java.util.*;
public class Main {
static int N;
static int[] popul;
static ArrayList<Integer>[] graph;
static int answer = 0;
static boolean[] chk;
static int totalP = 0;
static boolean answerFlag = false;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
popul = new int[N + 1];
graph = new ArrayList[N + 1];
chk = new boolean[N+1];
for (int i = 1; i <= N; i++) {
popul[i] = sc.nextInt();
graph[i] = new ArrayList<>();
answer += popul[i];
}
totalP = answer;
for (int i = 1; i <= N; i++) {
int link = sc.nextInt();
for (int idx=0; idx<link; idx++) {
graph[i].add(sc.nextInt());
}
}
int half = 0;
if ( N % 2 == 0) {
half = N/2;
} else {
half = N/2 +1 ;
}
for (int cnt=1; cnt<=half; cnt++) {
int[] comb1 = new int[cnt];
combination(cnt, 0, comb1, 1);
}
if (!answerFlag) System.out.println(-1);
else System.out.println(answer);
}
static void combination(int cnt, int idx, int[] tempArr, int start) {
if (idx == cnt) {
int[] region1 = Arrays.copyOf(tempArr, cnt);
if(linkChk(region1)) {
answerFlag = true;
int sum1 = 0;
for (int i: region1) {
sum1 += popul[i];
}
// System.out.println("totalP, sum1: "+totalP+" "+sum1);
answer = Math.min(answer, Math.abs((totalP - sum1)-sum1));
}
return;
}
for (int i=start; i<=N; i++) {
if (!chk[i]) {
chk[i] = true;
tempArr[idx] = i;
combination(cnt, idx+1, tempArr, i+1);
chk[i] = false;
}
}
}
static boolean linkChk(int[] region1) {
boolean[] visited = new boolean[N+1];
boolean[] tempChk = new boolean[N+1];
int[] region2 = new int[N-region1.length];
// System.out.println("확인 전: "+Arrays.toString(visited));
// 두 번째 지역 만들기
int idx = 0;
for (int i: region1) {
tempChk[i] = true;
}
for (int i=1; i<=N; i++) {
if (!tempChk[i]) region2[idx++] = i;
}
// bfs
// 1번 구역 확인
Queue<Integer> q = new LinkedList<>();
q.add(region1[0]);
visited[region1[0]] = true;
while(!q.isEmpty()) {
int curr = q.poll();
for (int i: graph[curr]) {
if (!visited[i] && tempChk[i]) {
q.add(i);
visited[i] = true;
}
}
}
// 2번 구역 확인
q = new LinkedList<>();
q.add(region2[0]);
visited[region2[0]] = true;
while(!q.isEmpty()) {
int curr = q.poll();
for (int i: graph[curr]) {
if (!visited[i] && !tempChk[i]) {
q.add(i);
visited[i] = true;
}
}
}
// System.out.println("region1: "+Arrays.toString(region1));
// System.out.println("region2: "+Arrays.toString(region2));
// System.out.println(Arrays.toString(visited));
// 모두 방문 체크 되어있는지 체크
for (int i=1; i<=N; i++) {
if (!visited[i]) return false;
}
return true;
}
}