[백준] 17471 게리맨더링 - 조합(Combination) + DFS(깊이우선탐색) + 유니온파인드(Union Find) + 구현 JAVA

passionfruit200 2023. 11. 29. 10:00

2023. 11. 29. 10:00

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

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

passionfruit200