https://www.acmicpc.net/problem/17471
17471번: 게리맨더링
선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.
www.acmicpc.net
코드설명
조합(Combination) + DFS(깊이우선탐색) + 유니온파인드(Union Find) + 구현 을 활용하는 문제입니다.
문제에 대한 큰 그림은,
모든 가능한 선거구 나누기를 DFS 및 조합으로 탐색하면서, Union-Find를 사용하여 선거구를 연결하고 최소 인구 차이를 찾아내는 방식으로 구현합니다.
이떄 선거구 나누는 로직은, 어떤 선거구를 먼저 뽑느냐는 전혀 상관이 없으므로 단순히 DFS로 RED인지, BLUE인지 나눠주며 완전탐색시켜줍니다.
또한 이 문제는 Union-find가 아닌 BFS로도 가능합니다. 먼저 똑같이 그룹을 나눠줍니다.
이후에 visited 배열로 해당 배열이 아직 연결된 흔적이 없다면, 모두 연결을 시도합니다. 이떄 이 연결은 물론, 같은 그룹내에서만 작동되어야만 합니다. 또한, 이 연결이 시작되었다는 의미는 선거구가 하나의 덩어리로 나눠졌다는 것을 의미합니다. 이떄 나눠지는 부분이 2개일경우에만 2개의 선거구로 모두 연결된 상태라는 의미입니다. 3개라면, 해당 선거구에 동떨어진 선거구가 존재한다는 의미입니다.
개인적으로는 Union-Find를 사용하기에 적합한 문제라고 생각이 듭니다.
또한, Node 하나의 객체로 그룹의 정보, 사람의 개수, 연결된 그래프를 모두 처리함을 통해서 효율적으로 코딩할 수 있습니다.
코드를 구현하며 실수 & 고민했던 점입니다.
1. 각 마을의 선거구 그룹(1, 2) 를 group 배열에 따로 저장할까 아니면 Node에 저장할까에 대한 고민.
2. 각 마을을 Node로 표현하는것이 맞을까에 대한 고민.
3. Node = new Node[N]을 한뒤 ArrayList에서 그룹을 만들듯이 Node 생성자로 다시 메모리 초기화 시켜야주어야한다는점.
4. 마지막에 fidnParent로 갱신된 그룹을 하나의 통일된 부모로 맞춰주어야한다는점. 그래야만, 올바르게 그룹의 개수를 셀 수 있습니다.
5. 모든 조합을 완성했다면, 새로운 parent[i]=i 를 통해 새로 부모배열을 초기화시켜주어야합니다.
코드의 주요 로직입니다.
- DFS (깊이 우선 탐색):
- DFS 함수는 재귀적으로 호출되며, 현재 선거구의 번호를 가리키는 level을 인자로 받습니다.
- level이 N + 1이 되면 모든 선거구에 대한 그룹을 결정했다는 의미이기에 인구수 차이를 계산하기 위한 로직을 실행합니다.
- Union-Find
- 선거구를 그룹으로 나누기 위해 Union-Find 알고리즘을 사용합니다.
- findParent: 해당 선거구가 속한 그룹의 부모를 찾고, 해당 그룹의 부모의 번호로 해당 선거구를 갱신합니다.
- unionFind: 두 선거구를 하나의 그룹으로 합치는 메서드입니다.
- 연결된 선거구 체크:
- DFS 함수 내에서 각 선거구가 연결된 선거구와의 그룹을 체크합니다.
- 연결된 선거구가 같은 그룹에 속하면서 같은 Parent를 가지고있지 않다면, ( 즉 Union-Find가 되지 않았다면 ), 두 선거구를 하나의 그룹으로 합칩니다.
- 그룹에 속한 선거구의 부모 통일:
- 최종적으로 그룹이 결정된 후에는 각 선거구의 부모를 통일시켜줍니다.
- 인구 차이 계산:
- 각 선거구의 그룹을 통일시켜 연결 여부를 확인한 후, 두 그룹의 인구수 차이를 계산합니다.
- 최종적으로 계산된 인구 차이가 현재까지의 최소 차이보다 작다면 업데이트합니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;
public class Main {
public static int N, M;
public static int[] arr;
public static int[] group;
public static int answer = 100*100 + 1;
public static Node[] nodeArr;
public static int[] parent;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
arr = new int[N + 1];
nodeArr = new Node[N + 1];
parent = new int[N + 1];
for(int i=1;i<=N;i++) {
parent[i] = i;
}
for(int i=1;i<=N;i++) {
nodeArr[i] = new Node();
}
st = new StringTokenizer(br.readLine());
for(int i=1;i<=N;i++) {
arr[i] = Integer.parseInt(st.nextToken());
nodeArr[i].peopleCnt = arr[i];
}
for(int i=1;i<=N;i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken()); //연결된 선거구의 개수
for(int j=1;j<=a;j++) {
int b = Integer.parseInt(st.nextToken()); //연결할 선거구.
nodeArr[i].connectedArr.add(b); //각 선거구를 연결합니다.
nodeArr[b].connectedArr.add(i); //각 선거구를 연결합니다.
}
}
DFS(1);
// System.out.println("===================");
// for(int i=1;i<=N;i++) {
// System.out.print(" "+nodeArr[i].group);
// }
// System.out.println();
if(answer == 100*100 + 1)
System.out.println(-1);
else
System.out.println(answer);
}
public static int findParent(int x) {
if( x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
public static void unionFind(int a, int b) {
a = findParent(a);
b = findParent(b);
if( a < b) parent[b] = a;
else parent[a] = b;
}
public static void DFS(int level) {
if(level == N+1) { //만약 N개 모두 바꾸었다면.
for(int i=1;i<=N;i++) {
parent[i] = i;
}
// System.out.println("===================");
// for(int i=1;i<=N;i++) {
// System.out.print(" "+nodeArr[i].group);
// }
// System.out.println();
// 지금까지 구역을 두개의 선거구로 나누었습니다.
int oneGroup = 0;
int twoGroup = 0;
//1. 각 구역은 두 선거구 중 하나에 포함되어야 합니다.
//2. 선거구는 구역을 적어도 하나 포함해야하고, 한 선거구에 포함되어있는 구역은 모두 연결되어있어야합니다.
//구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을때, 두 구역은 연결되어잇다고 합니다.
for(int i=1;i<=N;i++) {
Node temp = nodeArr[i];
for(int j=0; j<temp.connectedArr.size();j++) {
Node next = nodeArr[temp.connectedArr.get(j)];
//같은 그룹이면서 연결되어잇다면 UnionFind를 통해 하나의 그룹으로 집합으로 묶어줍니다.
if(temp.group == next.group && findParent(i) != findParent(temp.connectedArr.get(j))) {
unionFind(i, temp.connectedArr.get(j));
}
}
}
HashSet<Integer> hashset = new HashSet<Integer>();
for(int i=1; i<=N;i++) {
// System.out.print(" "+parent[i]);
findParent(i); //마지막으로 findParent로 모든 Parent를 통일시켜줍니다.
hashset.add(parent[i]);
}
if(hashset.size() >= 3) { //만약 3보다 크거나 같다면 연결되어있지 않은 선거구가 존재하므로 불가하다.
return ;
}
if(hashset.size() == 1) {
return ;
}
for(int i=1; i<=N; i++) {
if( nodeArr[i].group == 1) {
oneGroup += nodeArr[i].peopleCnt;
}else if(nodeArr[i].group == 2) {
twoGroup += nodeArr[i].peopleCnt;
}
}
int result = Math.abs(oneGroup - twoGroup);
answer = Math.min(answer, result);
return;
}
nodeArr[level].group = 1;
DFS(level + 1);
nodeArr[level].group = -1;
nodeArr[level].group = 2;
DFS(level + 1);
nodeArr[level].group = -1;
}
}
class Node{
int peopleCnt = 0; //인구수
int group = -1; //만약 1번 선거구라면 1, 2번 선거구라면 2 로 설정할 것 입니다.
ArrayList<Integer> connectedArr = new ArrayList<Integer>();
public Node(int peopleCnt) {
this.peopleCnt = peopleCnt;
}
public Node() {
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;
public class Main {
public static int N,M, K;
public static int answer = Integer.MAX_VALUE;
public static int[] arr;
public static Node[] node;
public static int RED = 1, BLUE = 2;
public static int[] parent;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
arr = new int[N + 1];
node = new Node[N + 1];
parent = new int[N+1];
for(int i=0;i<=N;i++) {
parent[i] = i;
node[i] = new Node(0, -1);
}
st = new StringTokenizer(br.readLine());
for(int i=1;i<=N;i++) {
node[i].people = Integer.parseInt(st.nextToken());
}
for(int i=1;i<=N;i++) {
st = new StringTokenizer(br.readLine());
int t = Integer.parseInt(st.nextToken());
for(int j=0;j<t;j++) {
int connected = Integer.parseInt(st.nextToken());
node[i].connectedArr.add(connected);
}
}
simulate(1);
if(answer == Integer.MAX_VALUE) {
System.out.println("-1");
}else {
System.out.println(answer);
}
}
public static void simulate(int level) {
if(level == N+1) {
for(int i=0;i<=N;i++) {
parent[i] = i;
}
for(int i=1; i<=N;i++) {
ArrayList<Integer> graph = node[i].connectedArr;
for(int j=0;j<graph.size();j++) {
if(node[i].group == node[graph.get(j)].group && findParent(i) != findParent(graph.get(j)) ) {
unionParent(i, graph.get(j));
}
}
}
for(int i=1; i<=N;i++) {
findParent(i);
}
//합친 후에 만약 findParent를 모두 했을떄 개수가 2개가 아닌, 3개이상이라면 해당 연결되지 않은 선거구가 존재하는 것 입니다.
HashSet<Integer> hashset = new HashSet<Integer>();
for(int i=1; i<=N;i++) {
hashset.add(parent[i]);
}
int redCnt = 0;
int blueCnt = 0;
if(hashset.size() >= 3) {
return ;
}
else if(hashset.size() == 1) {
return ;
}
else if(hashset.size() == 2) {
for(int i=1; i<=N;i++) {
if(node[i].group == RED) {
redCnt += node[i].people;
}else {
blueCnt += node[i].people;
}
}
int diff = Math.abs(redCnt - blueCnt);
answer = Math.min(answer, diff);
}
return ;
}
//순서는 중요하지 않다... 그렇다면, 단순히 group으로 나누자.
node[level].group = RED;
simulate(level + 1);
node[level].group = -1;
node[level].group = BLUE;
simulate(level + 1);
node[level].group = -1;
}
public static int findParent(int x) {
if( x == parent[x]) return x;
else return parent[x] = findParent(parent[x]);
}
public static void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if( a < b) {
parent[b] = a;
}else {
parent[a] = b;
}
}
}
class Node{
int people;
int group = -1;
ArrayList<Integer> connectedArr = new ArrayList<Integer>();
public Node(int people, int group) {
this.people = people;
this.group = group;
}
}'알고리즘 > Disjoint Set' 카테고리의 다른 글
| [백준] 10451 순열 사이클 - 유니온 파인드(UnionFind, Disjoint Set) + DFS(깊이우선탐색) JAVA (0) | 2024.07.30 |
|---|---|
| [백준] 20040 사이클 게임 - 트리(Tree) + 분리집합(disjoint set) + 유니온파인드(Union Find) JAVA (0) | 2023.11.24 |
| [백준] 10775 공항 - 유니온파인드(Union Find) + 그리디(greedy) JAVA (0) | 2023.09.06 |
| [백준] 4195 친구 네트워크 - 유니온파인드(Union Find) + 해쉬맵(HashMap) JAVA (0) | 2023.09.05 |
| [백준] 16562 친구비 - 유니온파인드(Union Find) + 최소조건(Minimum) JAVA (0) | 2023.09.05 |