백준 17471 - 게리맨더링
Updated:
Java
17471 번 - 게리맨더링
문제
백준시는 N개의 구역으로 나누어져 있고, 구역은 1번부터 N번까지 번호가 매겨져 있다. 구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.
아래 그림은 6개의 구역이 있는 것이고, 인접한 구역은 선으로 연결되어 있다.
두 선거구에 포함된 인구의 차이를 최소로 하려고 한다. 백준시의 정보가 주어졌을 때, 인구 차이의 최솟값을 구해보자.
접근 방법
방향 없는 그래프 이므로, 먼저 각 노드들의 연결을 나타내는 방법으로 2차원 배열을 사용하였다.
이후 부분집합으로 노드를 뽑아, 뽑은 노드와 뽑지 않은 노드가 각각 그래프로 연결되있는지 확인하여 가능한 방법인지 체크한다.
그래프가 연결 되어 있는지 확인하기 위해, 이전에 풀었던 연결 요소의 개수를 응용하였다.
만약 선거구가 2개로 잘 나누어지면, 이제 각 선거구의 인구 수 총 합의 차를 구하여, 그 중 최솟값을 구한다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int MAX_NUM = 987654321;
static int n, result = MAX_NUM;
static int[] value, nodes;
static int[][] graph;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk;
n = stoi(br.readLine());
value = new int[n + 1];
nodes = new int[n + 1];
graph = new int[n + 1][n + 1];
stk = new StringTokenizer(br.readLine());
for(int i = 1; i <= n; i++) {
value[i] = stoi(stk.nextToken()); // 각 노드들의 값을 받는다.
}
for(int i = 1; i <= n; i++) {
stk = new StringTokenizer(br.readLine());
int size = stoi(stk.nextToken());
for(int j = 0; j < size; j++) {
graph[i][stoi(stk.nextToken())] = 1; // 방향 없는 그래프를 나타낸다.
}
}
DFS(0,n,0);
if(result == MAX_NUM) // 결과 값이 Max이면 선거구를 2개로 나눌 방법이 없는 것이다.
System.out.println(-1);
else
System.out.println(result);
br.close();
}
static int[] chkNode_1, chkNode_2;
static void DFS(int lv, int size, int sum) {
// 뽑은 부분집합의 개수가 n개가 되면, 두 부분집합에 의한 노드들이 둘다 연결 되있는지 확인한다.
if(lv == n) {
chkNode_1 = nodes.clone();
boolean isDupli = false;
for(int i = 1; i <= n; i++) {
if(chkNode_1[i] == 0) {
// 0인 노드들이 서로 연결된 구역이 2개 이상일 때, 불가능한 방법이다
if(isDupli) {
return;
}
chkConnect(i, chkNode_1, 0);
isDupli = true;
}
}
chkNode_2 = nodes.clone();
boolean isDupli2 = false;
for(int i = 1; i <= n; i++) {
if(chkNode_2[i] == 1) {
// 1인 노드들이 서로 연결된 구역이 2개 이상일 때, 불가능한 방법이다
if(isDupli2) {
return;
}
chkConnect(i, chkNode_2, 1);
isDupli2 = true;
}
}
int oSum = 0;
for(int i = 1; i <= n; i++) {
if(nodes[i] == 0) {
oSum += value[i];
}
}
result = Math.min(result, Math.abs(oSum - sum));
return;
}
// 각 노드를 부분집합으로 하나씩 선택한다.
nodes[lv] = 1;
DFS(lv + 1, size, sum + value[lv]);
nodes[lv] = 0;
DFS(lv + 1, size, sum);
}
static void chkConnect(int s, int[] chkNode, int idx) {
// 각 노드가 뽑히지 않은(값이 0) 그래프이므로, 방문 했다면 1로 바꾼다.
if(idx == 0)
chkNode[s] = 1;
// 각 노드가 뽑힌(값이 1) 그래프이므로, 방문 했다면 0로 바꾼다.
else
chkNode[s] = 0;
for(int i = 1; i <= n; i++) {
if(graph[s][i] == 1 && chkNode[i] == idx) {
chkConnect(i, chkNode, idx);
}
}
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
또 다른 방법
4월 16일에 복습 겸, 다시 풀어보았다.
A, B구역을 나누는 방법은 비슷하지만 각 구역이 연결되어있는지 확인 하는것은 BFS로 사용하여 다르다.
각 노드의 인덱스에 값이 true, false로 A,B 구역을 나눈다.
A 구역의 노드를 하나씩 가져와 Queue에 넣어, BFS를 통해 갈 수 있는 모든 곳을 방문한다. B 구역도 A구역과 마찬가지로 갈 수있는 노드를 전부 방문한다.
이후 전체 노드의 방문 여부를 확인하여 다 방문하였으면 그래프가 알맞게 절반으로 나누어 진 것이고, 방문하지 못한 곳은 제대로 연결되지 못한 것이 된다.
한 노드에서 다른 노드를 찾아 갈 때, 조건 3개를 보는데
- 그래프가 연결되어 있는지
- 아직 방문하지 않았은 노드인지
- 각 구역에 속한 노드인지
를 확인하는게 핵심이다.
import java.util.*;
import java.io.*;
public class Main {
static int n, result = Integer.MAX_VALUE;
static int[] node;
static boolean[] sel;
static boolean[] vis;
static boolean[][] graph;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk;
n = stoi(br.readLine());
node = new int[n+1];
sel = new boolean[n+1];
graph = new boolean[n+1][n+1];
stk = new StringTokenizer(br.readLine());
for(int i = 1; i <= n; i++) {
node[i] = stoi(stk.nextToken());
}
int num;
for(int i = 1; i <= n; i++) {
stk = new StringTokenizer(br.readLine());
num = stoi(stk.nextToken());
for(int j = 0; j < num; j++) {
graph[i][stoi(stk.nextToken())] = true;
}
}
DFS(0);
if(result == Integer.MAX_VALUE)
System.out.println(-1);
else
System.out.println(result);
br.close();
}
// 구역을 나누어 본다.
private static void DFS(int lv) {
if(lv == n) {
Gary();
return;
}
sel[lv + 1] = true;
DFS(lv + 1);
sel[lv + 1] = false;
DFS(lv + 1);
}
static void Gary() {
int Asum = 0, Bsum = 0;
vis = new boolean[n+1];
// 먼저 A구역과 B구역의 인구수 차이를 구하였다.
for(int i = 1; i <= n; i++) {
if(sel[i])
Asum += node[i];
else
Bsum += node[i];
}
Queue<Integer> queue = new LinkedList<Integer>();
int curN;
// A 구역이 다 연결되어 있는지 확인
for(int i = 1; i <= n; i++) {
if(sel[i]) {
queue.add(i);
vis[i] = true;
break;
}
}
while(!queue.isEmpty()) {
curN = queue.poll(); // 현재 노드
for(int i = 1; i <= n; i++) {
// 그래프가 연결되어 있고, 방문하지 않았으며, A 구역에 속하였는지
if(graph[curN][i] && !vis[i] && sel[i]) {
vis[i] = true;
queue.add(i);
}
}
}
// B 구역이 다 연결되어 있는지 확인
for(int i = 1; i <= n; i++) {
if(!sel[i]) {
queue.add(i);
vis[i] = true;
break;
}
}
while(!queue.isEmpty()) {
curN = queue.poll(); // 현재 노드
for(int i = 1; i <= n; i++) {
// 그래프가 연결되어 있고, 방문하지 않았으며, B 구역에 속하였는지
if(graph[curN][i] && !vis[i] && !sel[i]) {
vis[i] = true;
queue.add(i);
}
}
}
// 방문하지 않은 노드가 있다면, 연결되지 않은 것
for(int i = 1; i <= n; i++) {
if(!vis[i])
return;
}
// 인구수의 차이
result = Math.min(result, Math.abs(Asum - Bsum));
return;
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
총평
난이도
⭐⭐⭐⭐★
후기
처음 접근한 방법은 트리로 나누어 지지 않고, 일자로만 노드들이 이어진다는 문제로 해결하지 못하였다.
블로그의 흰트를 얻어, 해결하였다.
4월 16일
이번에는 저번 풀이와 달리 혼자 생각하여 풀어보았다.
확실히 남의 코드를 참고하여 푼 문제는 생각이 잘 안나게 된다.
개선할 점
없
