BOJ_17471_게리맨더링

1

구분: BFS, DFS, 그래프 이론, 그래프 탐색, 부트포스 알고리즘

언어: Java

전략

 

1. 지역구 입력 받기 

• 연결 리스트의 형태로 지역구를 받는다. - 노드와 링크를 받을 클래스를 생성하였다. 

 

2. 지역구로 나누기

• 부분 집합을 구하는 방법으로 지역구 2개로 나눈다 - 부분 집합 하나만 선택하면, 포함되지 않는 것들끼리 또 하나의 부분 집합이 완성
• 부분 집합의 개수가 0이거나 n개일 경우는 제외한다.

 

3. 각 부분 집합이 연결되었는지 확인

• BFS를 이용하여 각 지역구가 연결 되었는지 확인한다 - 한 점에서 다른 점까지 도달 가능하면 지역구들은 연결되어 있는 것이다. 
• 두 지역구 각각 연결 여부를 확인해야 한다.

 

4. 차이 구하기 

• 각각의 구역의 인구 수들을 구해서 차이의 최소를 찾는다. 

---

2. 코드

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	//인접 리스트를 만들기 위한 노드 클래스
	static class Node{
		int v;
		Node link;
		Node(int v, Node link){
			this.link = link;
			this.v = v;
		}
	}
	static int n; //전체 노드 개수 
	static Node[] adjlist; //연결 리스트
	static int[] population; //인구 수 
	static boolean[] check, connect; //check: 부분집합 생성여부 판단 , connect: bfd를 통해 공들 인접여부 확인
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		n = scanner.nextInt();
		population = new int[n+1];
		int sum = 0;
		for(int i = 1; i<=n; i++) {
			population[i] = scanner.nextInt();
			sum+=population[i];
		}
		adjlist = new Node[n+1];
		
		for(int i = 1; i<=n; i++) {
			int num = scanner.nextInt();
			for(int j = 0; j<num; j++) {
				int v = scanner.nextInt();
				adjlist[i] = new Node(v, adjlist[i]);
			}
		}
		
		check = new boolean[n+1];
		
		subset(1);//인덱스로 이용을 하기 떄문에 1부터 시작
		
		if(min == Integer.MAX_VALUE)//분할할 수 없음
			System.out.println(-1);
		else
			System.out.println(min);

		
	}//main
	
	static int min = Integer.MAX_VALUE;
	
	private static void subset(int cnt) {
		
		if(cnt == n+1) {//부분집합 생성 완료
			
			int truecnt = 0;
			for(boolean b:check) {
				if(b) truecnt++;
			}
			int falsecnt = n - truecnt;
			
			
			//두 구역으로 나뉘지 않은 경우 
			if(truecnt==0 || truecnt==n)
				return;
			
			
			connect = new boolean[n+1];
			//bfs를 통해 공들 연결 여부 파악
			int qcntt = 0;
			Queue<Integer> q = new LinkedList<>();
			for(int i = 1; i<=n; i++) {
				//선택된 공 일단 하나 걍 넣는디
				if(check[i]) {
					q.offer(i);
					connect[i] = true;
					break;
				}
		
			}
			
			while(!q.isEmpty()) {
				
				int x = q.poll();
				qcntt++;
				
				for(Node temp = adjlist[x]; temp!=null; temp = temp.link) {
					if(!check[temp.v])continue; //같은 구역 아닌 것은 그냥 지나가 
					if(connect[temp.v])continue; //이미 방문한 곳이면 지나가
					q.offer(temp.v);
					connect[temp.v] = true;
				}
			}
			
			//내가 선택한 공들이 모두 연결된 공인지 확인
			boolean isconnect = true;
			for(int i = 1; i<=n; i++) {
				if(check[i]!=connect[i])
					{
						isconnect = false;
						break;
					}
			}
			if(qcntt != truecnt)
				isconnect = false;
			
			//연결 X -> 선거구로 나눌 수 없음
			if(!isconnect) return;
			
			
			//나머지 부분도 체크
			//bfs를 통해 공들 연결 여부 파악
			q.clear();
			int qcntf = 0;
			Arrays.fill(connect, false);
			
			for(int i = 1; i<=n; i++) {
				//선택안된 나머지 공 일단 하나 걍 넣는디
				if(!check[i]) {
					q.offer(i);
					connect[i] = true;
					break;
				}
			}
			
			while(!q.isEmpty()) {
				
				int x = q.poll();
				//connect[x] = true;
				qcntf++;
				
				//System.out.print(x+" ");
				
				for(Node temp = adjlist[x]; temp!=null; temp = temp.link) {
					if(check[temp.v])continue; //같은 구역 아닌 것은 그냥 지나가 여긴 선택 못받은 부분들이야!
					if(connect[temp.v])continue; //이미 방문한 곳이면 지나가
					q.offer(temp.v);
					connect[temp.v] = true;
				}
			}
			
			//내가 선택한 공들이 모두 연결된 공인지 확인
			isconnect = true;
			
			if(qcntf != falsecnt)
				isconnect = false;
			
			for(int i = 1; i<=n; i++) {
				if(check[i]==connect[i])
					{
						isconnect = false;
						//System.out.println("  여기가?: "+i);
						break;
					}
			}
			
			//연결 X -> 선거구로 나눌 수 없음
			if(!isconnect) return;
			
					
			//연결 확인 - 이제 인구 수 구해서 차 최소를 구하자
			int popsumt = 0;
			int	popsumf = 0;
			
			for(int i = 1; i<=n; i++) {
				if(check[i])
					popsumt+=population[i];
				else
					popsumf+=population[i];
			}
			
			int calc = Math.abs(popsumf - popsumt);
			min = calc<=min? calc:min;			
			return;
		}
		
		//부분 집합을 구하는 부분
		check[cnt] = true;
		subset(cnt+1);
		
		check[cnt] = false;
		subset(cnt+1);
		
	}
	
}//class

---

3

• 실전 문제 스럽다고 한다. 하지만 좀 쉬운 수준이라고 한다.(약 2시간 정도 소요)
• 처음에는 한 지역구만 연결 여부를 파악했다.
• 테케 2번 때문에 그래프가 하나라도 연결이 안되어 있으면 안된다고 생각했지만 테케 4번을 보고 내가 틀렸음을 알게 되었다.
• BFS를 이용하여 그래프 간의 연결을 확인하는 것을 이제 알겠다. 
• 부분 집합을 생성할 때, 그 배열의 시작이1 임을 인지하지 못하고 0 부터 해서 인덱스가 꼬였다.
• BFS 이용 시, 방문 처리를 하는 부분을 Queue에 삽입하고 해야 하는데, Queue에서 뺄 때 해버려서 오랜 시간 삽질을 하였다. 
• if문에 괄호를 두지 않고 여러 줄을 조건문에 걸어서 오랜 시간 힘들었다.