백준 17471 <게리맨더링>

2가지 선거구로 나누고 선거구가 연결되어있는지 확인하는 문제!

 

즉 부분집합을 구하고 각각의 선거구에서 BFS를 실행해서 연결되어 있는지 확인하는 것!!

 

반대로 생각을 하면 복잡하기도하고... 풀리지 않는 문제 ㅜㅜ 즉 문제를 많이 풀어봐야 한다.

 

 

선거구를 두 개로 나눈 것이다. 

 

이 cal 부분은 선거구가 두 개로 나뉘어서 연결되어 있는지 확인하는 코드이다.

 

두 개가 연결되었다면 count는 2가 될 것이고 값을 비교해서 넣어주게 된다.

 

인접 리스트를 이용해서 다음 노드가 같은 팀인지 확인하게 되고 같은 팀이라면 큐에 넣고 BFS를 실해해 주는 것이다.

 

이렇게 총 3단계를 이용해서 문제를 해결할 수 있다.

이 방법이 생각이 어떻게 나냐? 하는 사람들은 문제를 많이 풀어보길 권한다.

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{

	static int n,result,num[],result1[];
	static boolean visit[],team[];
	static ArrayList<Integer> a[];
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader kb = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(kb.readLine());
		num=new int[n+1];
		a=new ArrayList[n+1];
		team=new boolean[n+1];
		result=Integer.MAX_VALUE;
		for(int i=1;i<=n;i++) {
			a[i]=new ArrayList<Integer>();
		}
		StringTokenizer st = new StringTokenizer(kb.readLine());
		for(int i=1;i<=n;i++) {
			num[i]=Integer.parseInt(st.nextToken());
		}
		for(int i=1;i<=n;i++) {
			st = new StringTokenizer(kb.readLine());
			st.nextToken();
			while(st.hasMoreTokens()) {
				a[i].add(Integer.parseInt(st.nextToken()));
			}
		}
		go(1);
		if(result==Integer.MAX_VALUE) {
			System.out.println(-1);
		}
		else
			System.out.println(result);

	}

	private static void go(int i) {
		// TODO Auto-generated method stub
		if(i==n+1) {
			cal();
			return;
		}
		team[i]=false;
		go(i+1);
		team[i]=true;
		go(i+1);
	}

	private static void cal() {
		// TODO Auto-generated method stub
		 visit=new boolean[n+1];
		 result1=new int[2];
		 int count=0;
		for(int i=1;i<=n;i++) {
			if(!visit[i]) {
				if(count==2) {
					return;
				}
				visit[i]=true;
				bfs(i,count);
				count++;
			}
		}
		if(count==2)
			result=Math.min(result, Math.abs(result1[0]-result1[1]));
	}

	private static void bfs(int i,int who) {
		// TODO Auto-generated method stub
		Queue <Integer>q =new LinkedList<Integer>();
		q.add(i);
		while(!q.isEmpty()) {
			int next=q.remove();
			result1[who]+=num[next];
			for(int j=0;j<a[next].size();j++) {
				int ne=a[next].get(j);
				if(visit[ne]||team[next]!=team[ne])
					continue;
				visit[ne]=true;
				q.add(ne);
			}
		}
	}

}