[Unsolved][JAVA] 백준 17471 게리맨더링

반응형

https://www.acmicpc.net/problem/17471

17471번: 게리맨더링

 

1. 서론

 

아주 유명한 문제. 떠올리는 것에서 1차 고비, 구현하는 것에서 2차 고비가 온 문제다. 근데 막 엄청나게 어렵지는 않다!!

 

2. 문제 풀이

 

아주 전형적인 그래프 문제이다. 그래프가 주어지고 그걸 두 개의 구역으로 나누어서 그 그래프가 가지고 있는 값의 차가 가장 작은 값을 구하는 문제이다. 만약 나누는 것이 불가하다면 -1을 출력해야 한다.

 

입력에서 두 그래프가 연결되어 있다는 것을 0,1로 표시하는 것이 아니라 각 노드마다 어떤 노드와 연결되어 있는지를 입력으로 준다.

그래서 나는 ArrayList로 입력을 받았다. (들어오는 값이 불규칙하고 노드가 많아봤자 10개이기 때문에)

 

선거구를 나누는 방법은 바로 부분집합이다.

부분집합으로 1번 선거구를 뽑고 뽑히지 않은 곳을 2번 선거구로 지정해 그룹을 나눈다.

이때 주의할 점은 부분집합에는 공집합도 포함이 되는데 공집합인 경우에는 나머지 한쪽이 전부인 경우이므로 선거구가 나뉘지 않았기 때문에 따로 처리해줘야 한다.

 

선거구를 두 개로 나누고 나서는 이 선거구들이 다 연결되어 있는지 체크를 해야 한다. 나는 bfs, dfs 양쪽 모두를 한 번 돌려 봤다.

로직은 그냥 동일하다. 아까 입력받은 list를 돌면서 1번 선거구 혹은 2번 선거구 그 값이 있는지 없는지 체크해서 bfs인 경우에는 큐에 넣고, dfs인 경우에는 재귀로 방문해서 그 노드에 도달한 경우 방문 체크를 해주면 된다.

 

dfs, bfs로직이 끝난 후에는 어떤 노드를 방문했는지의 여부를 알 수 있기 때문에 전부 방문한 경우만이 두 선거구가 모두 연결된 경우이므로 최솟값 계산을 시작한다. 두 선거구의 차를 구해주면 된다.

 

3. 코드 설명

 

 

- dfs인 경우

import java.io.*;
import java.util.*;

public class Main {
	
	static int n, ans;
	static int[] num;
	static boolean[] select;
	static List<List<Integer>> map;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		n = Integer.parseInt(br.readLine());
		
		num = new int[n + 1]; //각 마을의 유권자
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= n; i++)
			num[i] = Integer.parseInt(st.nextToken());
		
		map = new ArrayList<>();
		for (int i = 0; i <= n; i++)
			map.add(new ArrayList<>());
		
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			for (int j = 0; j < x; j++)
				map.get(i).add(Integer.parseInt(st.nextToken())); //각 마을마다 연결된 마을 저장
		}

		select = new boolean[n + 1];
		ans = Integer.MAX_VALUE;
		subset(0);
		if (ans == Integer.MAX_VALUE) //없는경우 -1
			ans = -1;
		System.out.println(ans);
	}
	
	public static void dfs(int idx, List<Integer> area, boolean[] v) {// 각 선거구마다 서로 연결되어 있는지 확인
		v[idx] = true; //방문한 경우 방문 체크
		for (int i = 0; i < area.size(); i++) 
			for (int j = 0; j < map.get(idx).size(); j++)
				if(map.get(idx).get(j)== area.get(i) && !v[area.get(i)])
					dfs(area.get(i), area, v);
	}
	
	public static void subset(int cnt) {
		if (cnt == n + 1) { //1~n까지이기 때문에
			List<Integer> first = new ArrayList<>(); //1번 선거구
			List<Integer> second = new ArrayList<>(); //2번 선거구
			
			for (int i = 1; i <= n; i++)
				if (select[i])
					first.add(i);
				else
					second.add(i);
			
			if (first.isEmpty() || second.isEmpty()) return; //공집합인 경우 2개로 나누어진 것이 아니므로 제외
			
			boolean[] visit = new boolean[n + 1];//방문체크
			dfs(first.get(0), first, visit); //1선거구 방문체크
			dfs(second.get(0), second, visit); //2선거구 방문체크
			
			boolean f = true;
			for (int i = 1; i <= n; i++)
				if (!visit[i]) f = false; //전부 다 방문하지 않았다면 전부 연결되어 있지 않다는 뜻
			
			if (f) { //연결되어 있는 경우에만 최솟값 계산
				int a = 0, b = 0;
				
				for (int i = 0; i < first.size(); i++) 
					a += num[first.get(i)];
				for (int i = 0; i < second.size(); i++) 
					b += num[second.get(i)];
				
				ans = Math.min(ans, Math.abs(a - b)); //두 선거구의 유권자 수 최솟값
			}
			return;
		}
		
        //부분집합으로 선거구 2개로 나누기
		select[cnt] = true;
		subset(cnt + 1);
		select[cnt] = false;
		subset(cnt + 1);
	}
}

 

 

- bfs인 경우

 

import java.io.*;
import java.util.*;

public class Main {
	
	static int n, ans;
	static int[] num;
	static boolean[] select;
	static List<List<Integer>> map;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		n = Integer.parseInt(br.readLine());
		
		num = new int[n + 1]; //각 마을의 유권자
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= n; i++)
			num[i] = Integer.parseInt(st.nextToken());
		
		map = new ArrayList<>();
		for (int i = 0; i <= n; i++)
			map.add(new ArrayList<>());
		
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			for (int j = 0; j < x; j++)
				map.get(i).add(Integer.parseInt(st.nextToken())); //각 마을마다 연결된 마을 저장
		}

		select = new boolean[n + 1];
		ans = Integer.MAX_VALUE;
		subset(0);
		if (ans == Integer.MAX_VALUE) //없는경우 -1
			ans = -1;
		System.out.println(ans);
	}
	
	public static void bfs(int idx, boolean[] visit, List<Integer> area) {
		Queue<Integer> q = new ArrayDeque<>();
		q.add(idx);
		
		while(!q.isEmpty()) {
			int x = q.poll();
			visit[x] = true;// 방문체크
			
			for (int i = 0; i < area.size(); i++)
				for (int j = 0; j < map.get(x).size(); j++)
					if(map.get(x).get(j)== area.get(i) && !visit[area.get(i)])
						q.add(area.get(i)); //연결되어있고, 방문하지 않은 경우에만 큐에 넣기
		}
	}
	
	public static void subset(int cnt) {
		if (cnt == n + 1) { //1~n까지이기 때문에
			List<Integer> first = new ArrayList<>(); //1번 선거구
			List<Integer> second = new ArrayList<>(); //2번 선거구
			
			for (int i = 1; i <= n; i++)
				if (select[i])
					first.add(i);
				else
					second.add(i);
			
			if (first.isEmpty() || second.isEmpty()) return; //공집합인 경우 2개로 나누어진 것이 아니므로 제외
			
			boolean[] visit = new boolean[n + 1];//방문체크
            bfs(first.get(0), visit, first);//1선거구 방문체크
			bfs(second.get(0), visit, second);//2선거구 방문체크
			
			boolean f = true;
			for (int i = 1; i <= n; i++)
				if (!visit[i]) f = false; //전부 다 방문하지 않았다면 전부 연결되어 있지 않다는 뜻
			
			if (f) { //연결되어 있는 경우에만 최솟값 계산
				int a = 0, b = 0;
				
				for (int i = 0; i < first.size(); i++) 
					a += num[first.get(i)];
				for (int i = 0; i < second.size(); i++) 
					b += num[second.get(i)];
				
				ans = Math.min(ans, Math.abs(a - b)); //두 선거구의 유권자 수 최솟값
			}
			return;
		}
		
        //부분집합으로 선거구 2개로 나누기
		select[cnt] = true;
		subset(cnt + 1);
		select[cnt] = false;
		subset(cnt + 1);
	}
}

 

코드 설명은 위에서 자세히 했기 때문에 + 주석이 있기 때문에 생략!!!!