[백준 17471] 골드5 - 게리맨더링

www.acmicpc.net/problem/17471

17471번: 게리맨더링

풀이시간 : 1시간

1. 유형

BFS, 조합

 

2. 풀이

노드가 10개 밖에 되지 않으니깐, 조합으로 레드팀과 블루팀으로 나눈다. 그 후, BFS를 돌려서 판단

 

3. 코드

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

public class back_17471게리맨더링 {
	static ArrayList<Integer> list[];
	static int person[];
	static int type[], n,answer=Integer.MAX_VALUE;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		list = new ArrayList[n+1];
		person = new int[n+1];
		type = new int[n+1];
		for (int i = 1; i <= n; i++) {
			person[i] = sc.nextInt();
		}
		for (int i = 1; i <= n; i++) {
			list[i] = new ArrayList<Integer>();
			int tmp=sc.nextInt();
			for (int j = 0; j < tmp; j++) {
				list[i].add(sc.nextInt());
			}
		}
		comb(1,0,0,0,0);
		if(answer == Integer.MAX_VALUE)
			System.out.println(-1);
		else
			System.out.println(answer);
	}
	
	static void comb(int arridx, int rednum,int bluenum, int redsum,int bluesum) {
		if(arridx==n+1) {
			if(rednum==0 ||bluenum==0) return;
			if(bfs(1) == rednum && bfs(2)==bluenum) {
				int tmp=Math.abs(redsum-bluesum);
				answer= answer > tmp? tmp: answer; 
			}
			return;
		}
		type[arridx]=1;
		comb(arridx+1, rednum+1, bluenum, redsum+person[arridx], bluesum);
		type[arridx]=2;
		comb(arridx+1, rednum, bluenum+1, redsum, bluesum+person[arridx]);
	}
	
	static int bfs(int color) {
		boolean visit[] = new boolean[n+1];
		int idx=0;
		for (int i = 1; i < n+1; i++) {
			if(type[i]==color) {
				idx=i;
				break;
			}
		}
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(idx);
		visit[idx] =true;
		int cnt=0;
		while(!q.isEmpty()) {
			int from = q.poll();
			cnt++;
			for (int i = 0; i < list[from].size(); i++) {
				int to = list[from].get(i);
				if(visit[to]) continue;
				if(type[to]!=color) continue;
				visit[to]=true;
				q.add(to);
			}
		}
		return cnt;
	}
}
//조합선택
//시작점에 대해서 bfs두번돌리기 각 길이가 같으면 성공

//comb arridx, rednum, bluenum redsum, bluesum
	//if arridx == n
		//if bfs(1) == rednum && 블루
			//abs redsum-bluesum
			//answer 갱신
	
	//type[arridx]=1
	//comb arridx+1, rednum+1, bluenum
	
	//type[arridx]=2
	//comb arridx+1, rednum, bluenum+1
	
	

//bfs int color
	//queue
	//visit
	//while
		//poll
		//cnt++
		//for n
			//if visit
			//if type[nextidx] != color continue
			//visit = true
			//add
	//return nt

//dfs
	//for
		//

 

인접리스트 만들기

		for (int i = 1; i <= n; i++) {
			list[i] = new ArrayList<Integer>();
			int tmp=sc.nextInt();
			for (int j = 0; j < tmp; j++) {
				list[i].add(sc.nextInt());
			}
		}

 

레드팀과 블루팀 조합을 나눈다. 파라미터로는 배열인덱스, 각 팀을 뽑은수, 각 팀의 인구수를 설정했다.

type[arridx]=1;
comb(arridx+1, rednum+1, bluenum, redsum+person[arridx], bluesum);
type[arridx]=2;
comb(arridx+1, rednum, bluenum+1, redsum, bluesum+person[arridx]);

 

기저조건으론 노드의 끝에 도달하면, 영역의 갯수가 0인 경우는 제외하고 레드팀과 블루팀을 기준으로 bfs를 돌린다

만약 bfs에서 리턴한 구역의 갯수와 뽑은 갯수가 같다면 성공이다

		if(arridx==n+1) {
			if(rednum==0 ||bluenum==0) return;
			if(bfs(1) == rednum && bfs(2)==bluenum) {
				int tmp=Math.abs(redsum-bluesum);
				answer= answer > tmp? tmp: answer; 
			}
			return;
		}

 

bfs에서는 인접리스트를 탐색하면서 노드가 연결됐고, 방문하지 않았고, 구역의 색이 같다면 이동가능하다

			for (int i = 0; i < list[from].size(); i++) {
				int to = list[from].get(i);
				if(visit[to]) continue;
				if(type[to]!=color) continue;
				visit[to]=true;
				q.add(to);
			}