[골드4] 17471. 게리맨더링 (Java)
https://www.acmicpc.net/problem/17471
17471번: 게리맨더링
선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.
www.acmicpc.net
달려보자
※ 문제를 요약하면 아래와 같습니다.
▶ 1번 부터 N번의 구역이 존재, 이 구역들을 두 선거구로 나눠야 함
▶ 이 때 각 선거구안의 구역들은 반드시 연결 되어 있는 상태
ex) 1~6번까지의 구역이 아래와 같이 연결되어 있을 때
▶ 각 구역에 사람의 수가 입력되어있으며, 두 선거구에 인구의 차이를 최소화 하려함
▶ 구역에 대한 정보가 주어졌을 때, 인구 차이의 최소값 탐색
▶ Input : 첫째 줄에 구역의 갯수 N, 다음 줄에 구역 별 사람 수,
셋째 줄 부터 N개의 줄에 각 구역에 인접한 구역의수, 연결된 구역 번호가 입력
▶ Output : 두 선거구로 나누었을 때 인구 차이의 최소값 출력
◈ Input - 1
6
5 2 3 4 1 2
2 2 4
4 1 3 6 5
2 4 2
2 1 3
1 2
1 2◈ Output - 1
1◈ Input - 2
6
1 1 1 1 1 1
2 2 4
4 1 3 6 5
2 4 2
2 1 3
1 2
1 2◈ Output - 2
0◈ Input - 3
6
10 20 10 20 30 40
0
0
0
0
0
0◈ Output - 3
-1◈ Input - 4
6
2 3 4 5 6 7
2 2 3
2 1 3
2 1 2
2 5 6
2 4 6
2 4 5◈ Output - 4
9◎ 코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.
▶ 0~N-1 (1~N) 까지 두 가지로 나눌 수 있는 모든 경우의 수 탐색
▶ 위의 경우의 수는 재귀 형태로 구현, 1~ N/2 크기 만큼 번호를 선택하여 1번 구역
선택되지 않은 구역은 2번 구역으로 나누어 각 구역의 노드들이 연결 되어 있는지 확인\
ex) Input- 1
[1,4], [2,3,5,6] 은 가능한 1, 2번 구역의 노드들이 연결되어 있으므로 구역 나누기 가능
[1,2], [3,4,5,6] 은 3,4 번과 5,6 번이 연결 되어 있지 않으므로 구역 나누기 불가능
▶ 첫번째 배열의 크기를 1부터 N/2까지 크기에 대해 전부 재귀 탐색을 진행하여 경우의 수 탐색
( 코드 내 nPerm 변수 )
ex) [1,2,3] / [4,5,6] 과 [4,5,6] / [1,2,3]
[2] / [1,3,4,5,6] 과 [1,3,4,5,6] / [2] 등등 은 그룹의 순서가 바뀌어도 구분된 노드들이 같기 때문
▶ 두 가지로 나눈 경우의 수에 대해 각 구역들이 연결되어있는지 탐색
1. 조합에서 선택된 번호와 선택되지 않은 번호의 [0]번 인덱스를 시작으로 DFS진행 ( 코드 내 IsConnected 함수)
2. 2번의 DFS가 끝난 후 방문되지 않은 노드 존재 == 각 선거구 내부의 노드가 서로 연결이 되어 있지 않음
해당 경우는 선거구를 두 구역으로 나눌 수 없음
ex) Input-1
Case : [1,2], [3,4,5,6] => DFS로 1, 3 번 탐색 시 5,6번이 방문되지 않는다 == 연결이 되어 있지 않다.
3. 모두 방문 했을 경우 각 선거구의 인원수를 합하여 차이를 비교, 최소값과 비교하여 저장
4. 모든 케이스에 대하여 1~3번 반복
▶ 최소값 출력
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N, nMin, nPerm;
static ArrayList<ArrayList<Integer>> listNode;
static int[] narrPeople;
static boolean[][] barrVisit;
static int[] narrNums;
static int[] narrAnothers;
static boolean[] barrNums;
static boolean[] barrDFS;
public static void main(String[] args) throws IOException {
BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));
// 노드 입력 받고
N = Integer.parseInt(bReader.readLine());
listNode = new ArrayList<>();
for (int i = 0; i < N; i++) {
listNode.add(new ArrayList<>());
}
narrPeople = new int[N];
// 인구수 입력 받자
StringTokenizer st = new StringTokenizer(bReader.readLine());
for (int i = 0; i < N; i++)
narrPeople[i] = Integer.parseInt(st.nextToken());
// 구역 간의 관계를 (노드 관계) 입력 받자
for (int i = 0; i < N; i++) {
st = new StringTokenizer(bReader.readLine());
int nNodeCount = Integer.parseInt(st.nextToken());
for (int j = 0; j < nNodeCount; j++) {
int nNextNode = Integer.parseInt(st.nextToken()) - 1;
listNode.get(i).add(nNextNode);
}
}
nMin = Integer.MAX_VALUE;
// 일단 나눌 수 있는 경우의 수
// 절반까지만 탐색하면 나머지 절반은 이미 나눠본적 있는 그룹이므로 탐색할 필요가 없다
nPerm = 1;
while (nPerm <= N / 2) {
narrNums = new int[nPerm];
barrNums = new boolean[N];
narrAnothers = new int[N - nPerm];
getCases(0);
nPerm++;
}
if (nMin == Integer.MAX_VALUE)
nMin = -1;
bWriter.write(String.valueOf(nMin));
bWriter.close();
}
private static void getCases(int nIndex) {
// 기저 조건
if (nIndex == nPerm) {
// 두가지 케이스로 나눴을 경우
// 각 케이스 안의 노드들 끼리 연결 되있는지 확인해보자
// 조합에 뽑히지 않은 나머지
int nAnotherIdx = 0;
for (int i = 0; i < N; i++) {
if (!barrNums[i])
narrAnothers[nAnotherIdx++] = i;
}
// 두 개로 나눈 노드의 그룹이 연결되어있다면
// 사람 수 차이를 비교해보자
if (IsConnected()) {
int nSumFirst = 0;
int nSumSecond = 0;
for (int i = 0; i < nPerm; i++)
nSumFirst += narrPeople[narrNums[i]];
for (int i = 0; i < N - nPerm; i++)
nSumSecond += narrPeople[narrAnothers[i]];
int nResult = Math.abs(nSumFirst - nSumSecond);
// 인구 차이가 최소인 것 받아놓자
if (nMin > nResult) {
nMin = nResult;
}
}
return;
}
// 재귀 조건
// 일단 조합 뽑자
for (int i = nIndex; i < N; i++) {
if (!barrNums[i]) {
barrNums[i] = true;
narrNums[nIndex] = i;
getCases(nIndex + 1);
barrNums[i] = false;
}
}
}
// 두 시가지로 나눈 노드들이 연결되어 있는감
private static boolean IsConnected() {
boolean bResult = true;
// 조합에서 꺼낸 경우의 수 부터
// 연결 되어 있는지 봅시다
barrDFS = new boolean[N];
DFS(narrNums[0], narrNums);
if (!bCheck(narrNums))
return false;
// 조합에 선택되지 않은 노드들이
// 연결 되어 있는지 봅시다
DFS(narrAnothers[0], narrAnothers);
if (!bCheck(narrAnothers))
return false;
// 여기까지 왔으면 반으로 나눈게 연결되어 있따.
return true;
}
// 조합에서 꺼낸 노드들을 탐색하자
private static void DFS(int nNode, int[] narrTemp) {
barrDFS[nNode] = true;
for(int i = 0; i < narrTemp.length; i++) {
if(listNode.get(nNode).contains(narrTemp[i]) && !barrDFS[narrTemp[i]])
DFS(narrTemp[i], narrTemp);
}
}
// 해당 배열들이 탐색이 되었는지 확인
private static boolean bCheck(int[] narrTemp) {
for(int i = 0; i < narrTemp.length; i++) {
if(!barrDFS[narrTemp[i]])
return false;
}
return true;
}
}Good Luck! (피드백 감사합니다!)