알고리즘52 :: 비트마스킹 으로 문제 접근하기(1)

최근 완탐 문제를 해결하면서 팀 나누기(스타트링크, 링크와스타트, 게링맨더링 등) 에 비트마스킹을 적용하고 해결하고 싶었습니다. 

 

그래서 여러 강의와 문서들을 참고하였습니다. 

 

for(int i=0; i<(1<<4); i++) {
			System.out.println("i :" +i);
			for(int j=0; j<4; j++) {
				if((i&(1<<j))==0) {
					System.out.println("first : "+ j);
				}else {
					System.out.println("second : "+ j);
				}
				System.out.println();
			}
		}
	}

n = 4 일때 i의 값에 따라서 j 와 비트마스킹 연산을 통해 팀 나누기를 할 수 있습니다. 

위 결과는 

i :0
first0
first1
first2
first3

i :1
second0
first1
first2
first3

i :2
first0
second1
first2
first3

i :3
second0
second1
first2
first3

i :4
first0
first1
second2
first3

i :5
second0
first1
second2
first3

i :6
first0
second1
second2
first3

i :7
second0
second1
second2
first3

i :8
first0
first1
first2
second3

i :9
second0
first1
first2
second3

i :10
first0
second1
first2
second3

i :11
second0
second1
first2
second3

i :12
first0
first1
second2
second3

i :13
second0
first1
second2
second3

i :14
first0
second1
second2
second3

i :15
second0
second1
second2
second3

 

추가적으로 무엇을 더 공부해야 할것 같은 느낌이 들지만 이쯤만 하고 문제 해결에 집중해 보겠습니다.

 

스타트링크 문제에 bitmask 를 적용하여 해결 할 수 있습니다. 

 

package backjun;

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


public class 스타트와링크_bitmask {

	static int n ;
	static int[][] map;
	static ArrayList<Integer> al;
	static ArrayList<Integer> al2;
	static int ans = Integer.MAX_VALUE;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		StringTokenizer st = null;
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}//end of for loop
		
		//bitmask
		int c=-987654321;
		for(int i=0; i<(1<<n); i++) { //1~15 까지 다봄
			c = 0;
			for(int j=0; j<n; j++) {
				if((i & (1<<j))== 0) {
					//정확히 반을 나눴을 경우만 체크해주기 위함
					c+=1;
				}
			}//end of second loop
			
			if(c!=n/2) continue;
			
			al = new ArrayList<>();
			al2 = new ArrayList<>();
			
			for(int j=0; j<n; j++) {
				if((i & (1<<j))==0) {
					//팀 1
					al.add(j);
				}else {
					//팀 2
					al2.add(j);
				}
			}//end of for loop
			
			int team1 = 0;
			for(int z=0; z<al.size(); z++) {
				for(int j=0; j<al.size(); j++) {
					if(al.get(z)==al.get(j)) continue;
					team1 += map[al.get(z)][al.get(j)];
				}
			}
			int team2 = 0;
			for(int z=0; z<al2.size(); z++) {
				for(int j=0; j<al2.size(); j++) {
					if(al2.get(z)==al2.get(j)) continue;
					team2 += map[al2.get(z)][al2.get(j)];
				}
			}
			if(ans>Math.abs(team1-team2))
				ans = Math.abs(team1-team2);
			
			
		}
		//System.out.println(13 & ((1<<1))); -> 안맞으면 0 
		System.out.println(ans);
	}

}