[BOJ] - 게리맨더링 / 17471번 (Java)
1. 문제 접근
총 N개의 구역(노드)이 주어지고, 주어진 구역에 대해 인구수 차이가 최소가 되도록 2개의 영역으로 분할하였을 때 인구수의 차이를 구하면 된다.
조건은 다음과 같다.
- 각 구역은 두 선거구 중 하나에 포함되어야 한다.
- 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다.
떠올린 방법은 조합(Combination)을 통한 완전 탐색이다.
입력값의 제한을 보게 되면, "2 ≤ N ≤ 10" 라고 명시되어있다.
따라서 최대 값인 N = 10일 때를 보면, 구역을 2개로 나누어야하고, 하나의 영역에는 한 개 이상의 구역이 포함 되어야하므로 10 Combination 1 ~ 9 까지의 모든 경우를 살펴보면 된다.
이 때, 조합(Combination)의 경우 N이 짝수일 경우 조합의 결과가 R을 기준으로 좌우 대칭이므로 R의 탐색 범위를 줄일 수 있다.
// areaCnt Combination 1 ~ areaCnt Combination areaCnt - 1 까지 영역을 나누어보며 확인
for (int r = 1; r <= areaNumber / 2 + 1; ++r) {
R = r;
areaASelected = new int[r];
areaBSelected = new int[areaNumber - r];
makeCombination(0, 0, 0);
}
`areaASelected`는 A영역에 속하는 구역들 리스트이며, ` areaBSelected `역시 마찬가지다.
A영역에 한번 구역을 포함 시켜보고, B영역에 구역을 한번 포함시켜보며 모든 가능한 조합을 탐색하게 된다.
// 이번 영역(elementIdx)를 A에 배정
areaASelected[areaACnt] = elementIdx;
makeCombination(areaACnt + 1, areaBCnt, elementIdx + 1);
// 이번 영역(elementIdx)를 B에 배정
areaBSelected[areaBCnt] = elementIdx;
makeCombination(areaACnt, areaBCnt + 1, elementIdx + 1);
해당 조합 코드의 기저조건은 총 3가지가 있다.
- A영역, B영역 모두 선택했을 경우
- A영역만 모두 선택했을 경우
- B영역만 모두 선택했을 경우
각 상황에 따라 로직이 달라지게 되는데, 2번, 3번의 경우 최종적으로 1번 기저조건으로 모이게 된다.
2번의 경우 이후의 모든 구역을 A영역에 배정하고, 3번의 경우 이후의 모든 구역을 B영역에 배정하면 된다.
else if (areaACnt == R) {
// A영역만 모두 다 고른 경우 -> 나머지 다 B에 배정
areaBSelected[areaBCnt] = elementIdx;
makeCombination(areaACnt, areaBCnt + 1, elementIdx + 1);
return;
} else if (areaBCnt == areaNumber - R) {
// B영역만 모두 다 고른 경우 -> 나머지 다 A에 배정
areaASelected[areaACnt] = elementIdx;
makeCombination(areaACnt + 1, areaBCnt, elementIdx + 1);
return;
}
최종적으로 1번 기저조건에 도달하게 되면, 특정 조합이 완성된 것이므로 해당 조합의 유효성 검사(모든 구역이 이어져있는지)를 진행한 뒤, 인구수 합의 차이를 계산하여 갱신하면된다.
if (areaACnt == R && areaBCnt == areaNumber - R) {
areaAPeopleNum = 0;
areaBPeopleNum = 0;
isVisited = new boolean[areaNumber];
// 각 영역이 모두 연결 되어있는지 확인: A
if (!isConnected(areaASelected, 'A')) {
return;
}
// 각 영역이 모두 연결 되어있는지 확인: B
if (!isConnected(areaBSelected, 'B')) {
return;
}
// 최소 인구수 차이 갱신
ans = Math.min(ans, Math.abs(areaAPeopleNum - areaBPeopleNum));
return;
}
이 때, `isVisited[]` 방문 여부는 A영역의 방문 여부가 B영역의 결과에 영향을 미칠 수 있으므로 한번만 초기화를 진행한다.
모든 구역이 연결되어있는가 확인하는 방법은 BFS를 사용하였다.
기본적인 BFS에 영역에 따라 인구수를 저장하는 코드를 추가 하였다.
private static boolean isConnected(int[] areaList, char currArea) {
// 목표 탐색 노드 수
int targetNodeNum = areaList.length;
// 현재 탐색 노드 수
int searchNodeNum = 0;
Queue<Integer> q = new ArrayDeque<>();
if(areaList.length>0) {
q.offer(areaList[0]);
isVisited[areaList[0]] = true;
}
while (!q.isEmpty()) {
int currNode = q.poll();
++searchNodeNum;
// 인구수 추가
if (currArea == 'A') {
areaAPeopleNum += areaPeopleNumberList[currNode];
} else {
areaBPeopleNum += areaPeopleNumberList[currNode];
}
// 인접 노드 중에 동일 영역이 있다면 큐에 추가
for (int adNode : adList[currNode]) {
for (int sameArea : areaList) {
if (adNode == sameArea) {
if (isVisited[adNode])
continue;
q.offer(adNode);
isVisited[adNode] = true;
}
}
}
}
// 모든 영역이 연결되어있을 경우 true반화
if (targetNodeNum == searchNodeNum)
return true;
return false;
}
2. 코드
package boj;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
/**
* [BOJ] - 게리맨더링 / 17471번
* @author JinHxxxxKim
*
* 1. 구역의 개수 N을 입력받는다.
* 2. 구역의 인구가 1번 구역부터 N번 구역까지 순서대로 입력받는다.
* 3. 구역의 정보를 입력받는다.
*
* 총 구역의 개수가 10개를 넘지 않는다.
* 따라서 10 Combination 1 ~ 10 Combination 9까지 하나의 구역을 선택한 뒤 계산한다.
*
* 4. Combinaiton 함수를 호출한다.
* - 기저조건(areaACnt == 설정한 구역의 수 && areaBCnt == 설정한 구역의 수)
* - 선택된 구역(AREA A)에 대해 연결되어있는지 확인 연결되어있지 않다면 반환
* - 선택된 구역(AREA B)에 대해 연결되어있는지 확인 연결되어있지 않다면 반환
* - 위 두 조건이 모두 만족된다면, 인구수의 차를 구하고 최소값을 갱신한다.
*/
public class Sol_17471 {
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static StringTokenizer st;
private static int areaNumber; // 영역의 개수
private static int[] areaPeopleNumberList; // 인구수 저장 배열
private static List<Integer>[] adList; // 인접 리스트
// 조합 관련 변수
private static int R; // areaNumber Combination R
private static int[] areaASelected; // A영역에 속하는 영역 저장
private static int[] areaBSelected; // B영역에 속하는 영역 저장
private static int areaAPeopleNum; // A영역 인구수
private static int areaBPeopleNum; // B영역 인구수
private static int ans;
// BFS 관련 변수
private static boolean[] isVisited; // 방문 여부 확인 배열
public static void main(String[] args) throws Exception {
// 영역의 개수 입력
areaNumber = Integer.parseInt(br.readLine().trim());
areaPeopleNumberList = new int[areaNumber];
// 인구수 입력
st = new StringTokenizer(br.readLine().trim());
for (int areaCnt = 0; areaCnt < areaNumber; ++areaCnt) {
areaPeopleNumberList[areaCnt] = Integer.parseInt(st.nextToken());
}
adList = new List[areaNumber];
for (int areaCnt = 0; areaCnt < areaNumber; ++areaCnt) {
adList[areaCnt] = new ArrayList<Integer>();
}
// 그래프 상태 입력
for (int areaCnt = 0; areaCnt < areaNumber; ++areaCnt) {
st = new StringTokenizer(br.readLine().trim());
int adAreaNum = Integer.parseInt(st.nextToken());
for (int adCnt = 0; adCnt < adAreaNum; ++adCnt) {
adList[areaCnt].add(Integer.parseInt(st.nextToken()) - 1);
}
}
ans = Integer.MAX_VALUE;
// areaCnt Combination 1 ~ areaCnt Combination areaCnt - 1 까지 영역을 나누어보며 확인
for (int r = 1; r <= areaNumber / 2 + 1; ++r) {
R = r;
areaASelected = new int[r];
areaBSelected = new int[areaNumber - r];
makeCombination(0, 0, 0);
}
if (ans == Integer.MAX_VALUE)
System.out.println(-1);
else
System.out.println(ans);
}
/**
* 어떤 영역에 속할지 결정하는 메소드
*
* @param areaACnt 선택한 A영역의 개수
* @param areaBCnt 선택한 B영역의 개수
* @param elementIdx 이번에 선택할 영역 번호
*/
private static void makeCombination(int areaACnt, int areaBCnt, int elementIdx) {
// 기저조건
// 모두 선택완료
if (areaACnt == R && areaBCnt == areaNumber - R) {
areaAPeopleNum = 0;
areaBPeopleNum = 0;
isVisited = new boolean[areaNumber];
// 각 영역이 모두 연결 되어있는지 확인: A
if (!isConnected(areaASelected, 'A')) {
return;
}
// 각 영역이 모두 연결 되어있는지 확인: B
if (!isConnected(areaBSelected, 'B')) {
return;
}
// 최소 인구수 차이 갱신
ans = Math.min(ans, Math.abs(areaAPeopleNum - areaBPeopleNum));
return;
} else if (areaACnt == R) {
// A영역만 모두 다 고른 경우 -> 나머지 다 B에 배정
areaBSelected[areaBCnt] = elementIdx;
makeCombination(areaACnt, areaBCnt + 1, elementIdx + 1);
return;
} else if (areaBCnt == areaNumber - R) {
// B영역만 모두 다 고른 경우 -> 나머지 다 A에 배정
areaASelected[areaACnt] = elementIdx;
makeCombination(areaACnt + 1, areaBCnt, elementIdx + 1);
return;
}
// 이번 영역(elementIdx)를 A에 배정
areaASelected[areaACnt] = elementIdx;
makeCombination(areaACnt + 1, areaBCnt, elementIdx + 1);
// 이번 영역(elementIdx)를 B에 배정
areaBSelected[areaBCnt] = elementIdx;
makeCombination(areaACnt, areaBCnt + 1, elementIdx + 1);
}
private static boolean isConnected(int[] areaList, char currArea) {
// 목표 탐색 노드 수
int targetNodeNum = areaList.length;
// 현재 탐색 노드 수
int searchNodeNum = 0;
Queue<Integer> q = new ArrayDeque<>();
if(areaList.length>0) {
q.offer(areaList[0]);
isVisited[areaList[0]] = true;
}
while (!q.isEmpty()) {
int currNode = q.poll();
++searchNodeNum;
// 인구수 추가
if (currArea == 'A') {
areaAPeopleNum += areaPeopleNumberList[currNode];
} else {
areaBPeopleNum += areaPeopleNumberList[currNode];
}
// 인접 노드 중에 동일 영역이 있다면 큐에 추가
for (int adNode : adList[currNode]) {
for (int sameArea : areaList) {
if (adNode == sameArea) {
if (isVisited[adNode])
continue;
q.offer(adNode);
isVisited[adNode] = true;
}
}
}
}
// 모든 영역이 연결되어있을 경우 true반화
if (targetNodeNum == searchNodeNum)
return true;
return false;
}
}3. 디버깅
A 영역과 B영역의 크기를 설정하는 부분과 탐색을 진행하는 부분에 있어 `ArrayIndexOutOfBounds` 오류가 90% 쯤에서 발생하였다.
for (int r = 1; r <= areaNumber / 2 + 1; ++r) {
R = r;
areaASelected = new int[r];
areaBSelected = new int[areaNumber - r];
makeCombination(0, 0, 0);
}
`r`의 경우 `1`부터 `areaNumber / 2 + 1`까지 가능하다.
하지만 만약 `areaNumber`가 최소값인 2일 경우 `r`은 1, 2모두 가능하다.
그렇게 되면 A영역의 개수가 2개일 때, B영역의 개수는 0개가 된다.
B영역의 개수가 0개일 때 BFS 코드를 실행시키면 `ArrayIndexOutOfBounds` 오류가 발생한다.
private static boolean isConnected(int[] areaList, char currArea) {
...
Queue<Integer> q = new ArrayDeque<>();
if(areaList.length > 0) {
q.offer(areaList[0]);
isVisited[areaList[0]] = true;
}
...
}
주어진 배열에 대해 길이를 검증하지 않고 Queue에 삽입하고자 할 경우, 위와 같이 오류가 발생한다.
배열의 인덱스에 대해 직접 접근할 때 발생할 수 있는 예외 상황에 대해 조금 더 명확하게 코드를 작성할 필요가 있을 것 같다.
4. 결과
'알고리즘' 카테고리의 다른 글
| [BOJ] - 게임 개발 / 1516번 (Java) (0) | 2024.02.23 |
|---|---|
| [SWEA] - Contact / 1238번 (Java) (0) | 2024.02.22 |
| [SWEA] - 하나로 / 1251번 (Java) (0) | 2024.02.22 |
| [SWEA] - 최소 스패닝 트리 / 3124번 (Java) (0) | 2024.02.22 |
| [BOJ] - 암호 만들기 / 1759번 (Java) (0) | 2024.02.21 |