StartLink - BitMasking, BackTracking

문제 복기

백트랙킹 : 문제 조건에 부합하지 않거나 불가능한 경우 처리하지 않는다.

이 문제에서는 1번팀과 2번팀을 나눌 때, 1번팀의 갯수가 n/2가 아니면 처리할 필요가 없다. =>비트마스킹으로 모든 부분 수열을 생성하고, 그 부분 수열에서 0(또는 1)의 갯수를 세서, 그 부분수열에서 0의 갯수가 n/2가 아니면 1번팀, 2번팀에 추가/능력치 계산 연산을 하지 않도록 한다.

for(int i=0;i<(1<<n);i++ 문을 통해서 모든 부분수열을 다룬다. 각각의 부분 수열에서 0의 갯수를 저장할 cnt=0을 구현한다.

헷갈리는 개념

i-for문을 돌때 각각의 i는 각각의 부분수열을 의미한다! 그러므로 i-for문 안에서 각각의 부분수열마다 cnt를 구해주고, 그 부분수열의 cnt가 n/2가 아니면 아래 연산들을 수행하지 않도록 continue를 걸어준다!

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
        int[][] a = new int[n][n];
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        //비트마스킹.모든 부분집합 다 구한다.
        int ans = -1;
        for(int i=0;i<(1<<n);i++) {
        	int cnt=0;
        	for(int j=0;j<n;j++) {//각각의 부분집합에 대해 j번째가 0의 갯수 카운팅!
        		if((i&(1<<j))==0) {cnt++;}
        	}
        	if(cnt != n/2) continue;//갯수가 조건에 부합하는 부분수열들만 f 또는 s팀에 추가해준다.
        	ArrayList<Integer> f = new ArrayList<>();
        	ArrayList<Integer> s = new ArrayList<>();
        	for(int j=0;j<n;j++) {//각각의 부분집합에 대해 j번째가 0의 갯수 카운팅!
        		if((i&(1<<j))==0) {
        			f.add(j);
        		} else {s.add(j);}
        	}
        	int t1=0,t2=0;
            for(int l1=0;l1<n/2;l1++) {
            	for (int l2=0; l2<n/2; l2++) {
                    if (l1 == l2) continue;
                    t1 += a[f.get(l1)][f.get(l2)];
                    t2 += a[s.get(l1)][s.get(l2)];
                }
            }
            int diff = Math.abs(t1-t2);
            if(ans == -1||ans>diff) {
            	ans = diff;
            }
        }
        System.out.println(ans);
	}