[Java] 백준 17471 게리맨더링

Lee GaEun·2025년 8월 12일
JAVA 알고리즘백준

[Java] 알고리즘

목록 보기
91/93

17471 게리맨더링 문제 링크

#1

package week03;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.StringTokenizer;

public class BOJ_17471 {
	static ArrayList<ArrayList<Integer>> node;
	static int N, allPepole;
	static int[] population;
	static int gap;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		population = new int[N+1];
		allPepole = 0;
		for(int i=1; i<=N; i++) {
			population[i] = Integer.parseInt(st.nextToken());
			allPepole += population[i];
		}
		
		node = new ArrayList<>();
		for(int i=0; i<=N; i++) {
			node.add(new ArrayList<>());
		}
		
		int L;
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			L = Integer.parseInt(st.nextToken());
			for(int j=0; j<L; j++) {
				node.get(i).add(Integer.parseInt(st.nextToken()));				
			}
		}
		
		int gap = Integer.MAX_VALUE;
		Deque<Integer> list = new ArrayDeque<Integer>();
		boolean[] visited;
		int now, place1, place2;
		for(int i=1; i<=N; i++) {
			visited = new boolean[N+1];
			list.addLast(i);
			place1 = 0;
			place2 = allPepole;
			
			while(!list.isEmpty()) {
				now = list.pollFirst();
				visited[now] = true;
				
				place1 += population[now];
				place2 -= population[now];
				if(place1 > place2) {
					gap = Math.min(gap, place1-place2);
					break;
				}
				gap = Math.min(gap, place2-place1);
				
				for(int a : node.get(now)) {
					if(!visited[a]) {
						visited[a] = true;
						list.add(a);
					}
				}
			}
			
		}
		
		System.out.println(gap);
	}
}
  • 진짜 어림도 없음..
  • 이건 선거구가 무조건 하나로 엮여 있어야만 가능한 코드임

#2

package week03;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.StringTokenizer;

public class BOJ_17471 {
	static ArrayList<ArrayList<Integer>> node;
	static int N, allPepole;
	static int[] population;
	static int gap;
	static int[] parent;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// 구역의 수
		N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 구역 당 인구 수
		population = new int[N+1];
		// 모든 구역의 인구를 합친 수
		allPepole = 0;
		for(int i=1; i<=N; i++) {
			population[i] = Integer.parseInt(st.nextToken());
			allPepole += population[i];
		}
		
		// 연결 노드 자표형
		node = new ArrayList<>();
		for(int i=0; i<=N; i++) {
			node.add(new ArrayList<>());
		}
		
		// 연결 노드와 노드의 수 초기화
		int L;
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			L = Integer.parseInt(st.nextToken());
			for(int j=0; j<L; j++) {
				node.get(i).add(Integer.parseInt(st.nextToken()));				
			}
		}
		
		parent = new int[N+1];
		for(int i=1; i<=N; i++) {
			parent[i] = i;
		}
		// union-find로 구역 개수 탐색
		for(int i=1; i<=N; i++) {
			for(int j : node.get(i)) {
				union(i, j);
			}
		}
		boolean[] visited = new boolean[N+1];
		int section=0;
		for(int i=1; i<=N; i++) {
			find(i);
			if(!visited[parent[i]]) {
				visited[parent[i]] = true;
				section++;
			}
		}
		
//		System.out.println("section= " + section);
		
		if(section==1) {
			int gap = Integer.MAX_VALUE;
			Deque<Integer> list = new ArrayDeque<Integer>();
			int now, place1, place2;
			for(int i=1; i<=N; i++) {
				visited = new boolean[N+1];
				list.addLast(i);
				place1 = 0;
				place2 = allPepole;
				
				while(!list.isEmpty()) {
					now = list.pollFirst();
					visited[now] = true;
					
					place1 += population[now];
					place2 -= population[now];
					if(place1 > place2) {
						gap = Math.min(gap, place1-place2);
						break;
					}
					gap = Math.min(gap, place2-place1);
					
					for(int a : node.get(now)) {
						if(!visited[a]) {
							visited[a] = true;
							list.add(a);
						}
					}
				}
			}
			System.out.println(gap);
			
		} else if(section==2) {
			int place1=0, place2=0;
			int answer;
			for(int i=1; i<=N; i++) {
				if(parent[i]==parent[1]) {
					place1 += population[i];
				}
				else {
					place2 += population[i];
				}
			}
			answer = place1 > place2 ? place1-place2 : place2-place1;
			System.out.println(answer);
			
		} else {
			System.out.println(-1);
		}
		
	}
	
	public static void union(int x, int y) {
		int a = find(x);
		int b = find(y);
		
		if(a==b) {
			return;
		}
		else {
			parent[b] = a;
		}
	}
	
	public static int find(int x) {
		if(parent[x] == x) {
			return x;
		}
		
		parent[x] = find(parent[x]);
		return parent[x];
	}
}

  • 음.. union-find로 분리 가능한 선거구의 최소 개수를 구해서
  • 만약, 모든 노드가 이어져 있다면 결과 1 -> 위 코드대로
  • 만약, 두 구역으로 분리되어 있다면 결과 2 -> 두 구역 그대로 차 값 구함
  • 만약, 세 구역 이상이라면 결과 else -> -1 출력
  • 시간 초과 나더라도 틀리진 않을 줄 알았는데.. 음 코드가 복잡해서 어딘가에서 실수한 듯

#3

package forStudy;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.StringTokenizer;

public class BOJ_17471 {
	static ArrayList<ArrayList<Integer>> node;
	static int[] population;
	static int[] parent;
	static int N, answer;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// 구역의 수
		N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 구역 당 인구 수
		population = new int[N+1];
		// 모든 구역의 인구를 합친 수
		int allPepole = 0;
		for(int i=1; i<=N; i++) {
			population[i] = Integer.parseInt(st.nextToken());
			allPepole += population[i];
		}
		
		// 연결 노드 자표형
		node = new ArrayList<>();
		for(int i=0; i<=N; i++) {
			node.add(new ArrayList<>());
		}
		
		// 연결 노드와 노드의 수 초기화
		int L;
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			L = Integer.parseInt(st.nextToken());
			for(int j=0; j<L; j++) {
				node.get(i).add(Integer.parseInt(st.nextToken()));				
			}
		}
		
		answer = Integer.MAX_VALUE;
		boolean[] visited = new boolean[N+1];
		// 선거구 나누기
		findplace(1, visited);
		answer = answer==Integer.MAX_VALUE ? -1 : answer;
		System.out.println(answer);
		
	}
	
	public static void findplace(int level, boolean[] visited) {
		// 부분 수열 완성
		 if(level==N+1) {
			 ArrayList<Integer> a = new ArrayList<>();
			 ArrayList<Integer> b = new ArrayList<>();
			 
			 for(int i=1; i<=N; i++) {
				 if(visited[i]) {
					 a.add(i);
				 } else b.add(i);
			 }
			 
			 if(a.size()==0 || b.size()==0) return;
			 
			 int result1=0, result2=0;
			 // a와 b 구역 둘 다 요소가 모두 연결되어 있는 지 확인
			 if(union(a) && union(b)) {
//				 for(int i : a) {
//					 System.out.print("!!!!!!"+i+" ");
//				 }
//				 System.out.println();
//				 for(int i : b) {
//					 System.out.print("!!!!!!"+i+" ");
//				 }
				 for(int c : a) {
					 result1 += population[c];
				 }
				 for(int c : b) {
					 result2 += population[c];
				 }
				 
				 answer = Math.min((result1 > result2 ? result1 - result2 : result2 - result1), answer);
			 }
			 return;
		 }
		 
		 // 모든 부분 수열 모두 탐색
		 // 해당 요소를 선택 (a기준)
		 visited[level] = true;
		 findplace(level+1, visited);
		 // 해당 요소를 선택 X
		 visited[level] = false;
		 findplace(level+1, visited);
	}
	
	public static boolean union(ArrayList<Integer> list) {
		boolean[] visited = new boolean[N+1];
		Deque<Integer> a = new ArrayDeque<>();
		a.add(list.get(0)); 
		
		int now;
		while(!a.isEmpty()) {
			now = a.pollFirst();
//			System.out.println(now);
			visited[now] = true;
			
			for(int n : node.get(now)) {
				if(!visited[n]) {
					visited[n] = true;
					a.addLast(n);
				}
			}
		}
		
		for(int i : list) {
			if(!visited[i]) return false;
		}
		return true;
	}
}

  • 결국 풀이를 봤다..
  • N의 최댓값이 작아서 그런 지 부분 수열을 만드는 것도 연결되어 있는 지 확인하는 것도 모두 완탐으로 한다고 하더라..
  • 그래서 했는데 틀림.. ㅠ

#4

package week03;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.StringTokenizer;

public class BOJ_17471 {
	static ArrayList<ArrayList<Integer>> node;
	static int[] population;
	static int N, answer;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// 구역의 수
		N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 구역 당 인구 수
		population = new int[N+1];
		// 모든 구역의 인구를 합친 수
		for(int i=1; i<=N; i++) {
			population[i] = Integer.parseInt(st.nextToken());
		}
		
		// 연결 노드 자료형
		node = new ArrayList<>();
		for(int i=0; i<=N; i++) {
			node.add(new ArrayList<Integer>());
		}
		
		// 연결 노드와 노드의 수 초기화
		int L;
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			L = Integer.parseInt(st.nextToken());
			for(int j=0; j<L; j++) {
				node.get(i).add(Integer.parseInt(st.nextToken()));				
			}
		}
		
		answer = Integer.MAX_VALUE;
		boolean[] visited = new boolean[N+1];
		// 선거구 나누기
		findplace(1, visited);
		answer = answer==Integer.MAX_VALUE ? -1 : answer;
		System.out.println(answer);
		
	}
	
	public static void findplace(int level, boolean[] visited) {
		// 부분 수열 완성
		 if(level==N+1) {
			 ArrayList<Integer> a = new ArrayList<>();
			 ArrayList<Integer> b = new ArrayList<>();
			 
			 for(int i=1; i<=N; i++) {
				 if(visited[i]) {
					 a.add(i);
				 } else b.add(i);
			 }
			 
			 if(a.size()==0 || b.size()==0) return;
			 
			 int result1=0, result2=0;
			 // a와 b 구역 둘 다 요소가 모두 연결되어 있는 지 확인
			 if(union(a) && union(b)) {
				 for(int c : a) {
					 result1 += population[c];
				 }
				 for(int c : b) {
					 result2 += population[c];
				 }
				 
				 answer = Math.min((result1 > result2 ? result1 - result2 : result2 - result1), answer);
			 }
			 return;
		 }
		 
		 // 모든 부분 수열 모두 탐색
		 // 해당 요소를 선택 (a기준)
		 visited[level] = true;
		 findplace(level+1, visited);
		 // 해당 요소를 선택 X
		 visited[level] = false;
		 findplace(level+1, visited);
	}
	
	public static boolean union(ArrayList<Integer> list) {
		boolean[] visited = new boolean[N+1];
		Deque<Integer> a = new ArrayDeque<>();
		a.add(list.get(0)); 
		
		int now;
		while(!a.isEmpty()) {
			now = a.pollFirst();
			visited[now] = true;
			
			for(int n : node.get(now)) {
				if(!visited[n] && list.contains(n)) {
					visited[n] = true;
					a.addLast(n);
				}
			}
		}
		
		for(int i : list) {
			if(!visited[i]) return false;
		}
		return true;
	}
}
  • 반례 : 
입력 :
3
9 6 14
1 3
1 3
2 2 1

정답 : 
11

if(!visited[n]) {
	visited[n] = true;
	a.addLast(n);
}

  • 드디어 맞음....!

  • 해당 구역의 모든 노드가 연결되어 있는 지 확인하는 과정에서
  • n크기의 visited 배열로만 비교를 해주면 1-3-2로 연결되어 있는 경우에 1,2와 3이 다른 구역이 될 때 이음새가 없어지는 걸 체크해주지 못함
  • 1-3인 경우에 3은 다른 구역에 있기 때문에 방문 해주지 못함. 이렇게 해야 2 역시도 방문 불가능한 노드가 되기 때문에 visted 갱신이 안됨. -> 이게 맞는 로직
profile
Lee GaEun
I will give it my all (๑•̀o•́๑)ง
이전 포스트

[Java] SWEA 1249 보급로

다음 포스트

[Java] 백준 10800 컬러볼

0개의 댓글