[알고리즘] 게리맨더링

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

17471번: 게리맨더링

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static boolean[] comb;
	static List<Integer>[] graph;
	static int[] people;
	static int N;
	static int minPopulation;
	static boolean[] visited;
	static int truePopulation;
	static int falsePopulation;
	static int count = 0;
	static boolean flag;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		people = new int[N+1];
		st = new StringTokenizer(br.readLine());
		graph = new List[N+1];
		for (int i = 1; i <= N; i++) {
			graph[i] = new ArrayList<>();
		}
		for (int i = 1; i <= N; i++) {
			people[i] = Integer.parseInt(st.nextToken());
		}
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			int iter = Integer.parseInt(st.nextToken());
			for (int j = 0; j < iter; j++) {
				int a = Integer.parseInt(st.nextToken());
				graph[i].add(a);
			}
		}

		minPopulation = Integer.MAX_VALUE;
		comb = new boolean[N+1];
		dfs(1);
		if (minPopulation == Integer.MAX_VALUE) {
			System.out.println(-1);
		} else {
			System.out.println(minPopulation);
		}
	}

	private static void dfs(int depth) {
		if (depth == N+1) {
			int trueTarget = 0;
			int falseTarget = 0;
			int trueStart = -1;
			int falseStart = -1;
			for (int i = 1; i <= N; i++) {
				if (comb[i] == true) {
					trueTarget++;
					trueStart = i;
				} else {
					falseTarget++;
					falseStart = i;
				}
			}
			if (trueStart == -1 || falseStart == -1) {
				return;
			}
			visited = new boolean[N+1];
			visited[trueStart] = true;
			truePopulation = 0;
			count = 0;
			flag = false;
			isValid(trueStart, true, 1, trueTarget);
			boolean flag1 = flag;
			
			visited = new boolean[N+1];
			visited[falseStart] = true;
			falsePopulation = 0;
			count = 0;
			flag = false;
			isValid(falseStart, false, 1, falseTarget);
			boolean flag2 = flag;
			if (flag1 && flag2) {
				minPopulation = Math.min(minPopulation, Math.abs(truePopulation - falsePopulation));
			}
			return;
		}
		comb[depth] = false;
		dfs(depth+1);
		comb[depth] = true;
		dfs(depth+1);
	}

	private static void isValid(int start, boolean std, int depth, int target) {
		count++;
		if (std == true) {
			truePopulation += people[start];
		} else {
			falsePopulation += people[start];
		}
		
		if (count == target) {
			flag = true;
			return;
		}
		
		for (int next : graph[start]) {
			if (comb[next] == std && !visited[next]) {
				
				visited[next] = true;
				isValid(next, std, depth + 1, target);
				if (flag) {
					return;
				}
			}
		}
	}
}

나의 풀이

- 조합을 구하고 거기에 따라 순회를 하며 depth를 확인해주면 된다.

- 다만 착각한 부분이 있었는데 

private static void isValid(int start, boolean std, int depth, int target) {
		count++;
		if (std == true) {
			truePopulation += people[start];
		} else {
			falsePopulation += people[start];
		}
		
		if (count == target) {
			flag = true;
			return;
		}
		
		for (int next : graph[start]) {
			if (comb[next] == std && !visited[next]) {
				
				visited[next] = true;
				isValid(next, std, depth + 1, target);
				if (flag) {
					return;
				}
			}
		}
	}

위에서 return isValid라고 하고 제일 밑에서 return false를 했는데 내가 의도한 건 return true를 만났다면 바로 true로 리턴이 되도록 하는 것이다. 하지만 이렇게 하게 되면 for문이 끝나고 return false를 받아서 결과적으로 이전에 true 였던 값이 희석되게 되는 문제가 발생하였다. 이에 이를 해결하기 위해 flag를 도입하여 기저 조건을 만족하면 flag를 true로 만들어주고 다른 것들도 다 벗어나게 하였다.