공부 기록장

[백준-17471] 게리맨더링 본문

알고리즘/백준

[백준-17471] 게리맨더링

또도닝 2021. 4. 14. 10:07

이 문제는 백준 골드 5레벨 문제이다. 

 

 

 

사실 처음에 이 문제를 봤을때는 어떡해야하나.. 싶었는데 부분집합을 이용해서 A와 B집합에 들어갈 구역을 나눠주고, bfs를 이용해서 그 구역들이 연결되어 있는지 확인해보면 될 것 같았다. 근데 자꾸 인덱스초과가 나길래 도대체 나는 틀린곳이 없는데 왜 그런가.. 답답했었는데, 역시 내가 틀린거였다^^!

부분집합 구하는 부분에서 return값을 잘못줘서 그런 것이었다.

 

 

이 코드는 크게 3 부분으로 나눌 수 있는데, 

1. 입력받기 (main 문)

2. 부분집합 구하기 (powerset 부분)

3. 연결 되어있는지 확인 (bfs)

 

입력부터 살펴보자면,

LinkedList를 이용해서 입력을 받아주었다.

Point라는 클래스를 만들어서 그 안에 from, to, pop (나 자신, 연결 된 노드, 인구) 를 받아주고, 배열에 저장해주었다.

입력에서 가장 중요한 부분은, 아무곳에도 연결되지 않은 노드도 혼자서 지역을 가질 수 있기 때문에 자기 자신을 향하는 노드를 하나 추가해 준 것이다.

 

부분집합 구하기는

다른 부분집합 구하기와 크게 다르지 않다. boolean 배열과 재귀를 이용했다.

마지막으로 내가 원하는 만큼 다 뽑았으면 if문에서 처리를 해주는데, 처음에 이 부분에서 return을 잘못해서 계속해서 오류가 났었다. 

이 부분에서 내가 뽑은 배열들을 가지고 bfs를 돌려본다. bfs를 돌려서 연결 된 그래프라면 인구의 총 합이 나오고, 연결되지 않았다면 -1를 리턴해준다.

 

bfs 

이 부분도 지금까지 해왔던 bfs랑 크게 다르지 않다. 조금 다른 점이 있다면, 내가 뭘 뽑았는지 받아주고 뽑은 애들끼리 다 연결되어 있는지 확인해 주는 부분이 조금 다르다. 

 

 

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

public class 게리맨더링_17471 { //백준 골드5
	static int N, ans;
	static LinkedList<Point>[] list;
	static int[] population;
	static boolean[] visited;
	static boolean[] check; 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		ans = 100000;
		list = new LinkedList[N+1];
		population = new int[N+1];
		check = new boolean[N+1];
		
		list[0] = new LinkedList<Point>();
		for(int i=1; i<N+1; i++) {
			list[i] = new LinkedList<Point>();
			population[i] = sc.nextInt(); //노드 별 인구 수 받아주기
		}
		
		for(int i=1; i<N+1; i++) {
			int n = sc.nextInt(); //연결 된 노드 수
			for(int j=0; j<n; j++) {
				int to = sc.nextInt(); //연결된 노드
				list[i].add(new Point(i,to,population[i]));
			}
		}
		
		//아무곳에도 연결되지 않은 노드도 혼자서 지역을 가질 수 있기 때문에 추가.
		for(int i=1; i<N+1; i++) {
			list[i].add(new Point(i,i,population[i]));
		}
		
		powerset(0);
		
		if(ans == 100000)
			System.out.println("-1");
		else
			System.out.println(ans);
		
	}
	
	static void powerset(int cnt){
		if(cnt == N+1) {
			LinkedList<Integer> A = new LinkedList<>();
			LinkedList<Integer> B = new LinkedList<>();
			for(int i=1; i<cnt; i++) {
				if(check[i])
					A.add(i);
				else
					B.add(i);
			}
			
			//최소 1개 이상은 들어있어야 함.
			if(A.size() == 0 || B.size() == 0 )
				return;
			
			int a = bfs(A);
			if(a == -1) //만약 A부터 실패라면 B는 고려하지 않아도 됨.
				return;
			
			int b = bfs(B);
			if(b == -1)
				return;			
			
			if(Math.abs(a-b) < ans) {
				ans = Math.abs(a-b);
//				System.out.println(ans);
			}
			return;
		}
		
		check[cnt] = true;
		powerset(cnt+1);
		check[cnt] = false;
		powerset(cnt+1);
		
	}
	
	//검사하기
	static int bfs(LinkedList<Integer> l) {
		Queue<Point> q = new LinkedList<>();
		visited = new boolean[N+1];
		visited[l.peek()] = true;
		q.addAll(list[l.peek()]); //l에 들어있는 첫 숫자부터 시작.

		int cnt = 0;
		while (!q.isEmpty()) {
			Point p = q.poll();
			for(int i : l) {
				if(p.to == i && !visited[p.to]) {
					visited[p.to] = true;
					q.addAll(list[p.to]);
				}
			}
		}
		
		for(int i: l) {
			if(!visited[i]) //방문 안한곳이 있다면 연결 X
				return -1;
			else {
				cnt += list[i].peek().pop;
			}
		}
		
		return cnt;
	}
	
	static class Point{
		int from, to, pop;
		Point(int from, int to, int pop){
			this.from = from;
			this.to = to;
			this.pop = pop;
		}		
	}
}

'알고리즘 > 백준' 카테고리의 다른 글

[백준-16985] Maaaaaaaaaze  (0) 2021.04.21
[백준-16973] 직사각형 탈출  (0) 2021.04.16
[백준-9466] 텀 프로젝트  (0) 2021.04.12
[백준-1167] 트리의 지름  (0) 2021.04.08
[백준-1967] 트리의 지름  (0) 2021.04.08
Comments