[BOJ14889] 스타트와 링크

완전탐색 문제로 모든 경우의 수를 다 고려해야 하는 문제

두 팀의 능력치 차이만 구하면 되므로, 첫번째 사람은 무조건 스타트 팀에 속한다고 가정하고

2~N번째 사람을 DFS를 돌려서 답을 구할 수 있다

 

teamA(직관적이지 못한 변수명이다ㅠㅠ) 배열의 각 요소를 해당 사람이 A팀에 속했는지 여부라고 둘 수 있다.

 

만약 세 사람이 있다고 하면(| 아래는 각각의 상태에서 다시 DFS로 탐색할 경우)

 

(0)()

|

(01)(), (02)(), (03)()

|

(012)(), (013)(), (014)() ...

 

같은 라인에서는 for문을 사용해서 한 명씩 할당한다. 할당한 다음에는 다시 탐색을 시작해 다음 사람을 정하고

정확히 인원수의 절반을 A팀에 할당했다면 능력치 합을 구하는 base case로 넘어가도록 구현했다.

 

import java.util.*;

public class Main {
	static int[][] map;
	static boolean[] teamA;
	public static int DFS(int idx, int N, int member){
		int min = Integer.MAX_VALUE;
		int tmp = Integer.MAX_VALUE;
		
		if((int)(N/2) == member){
			int[] a = new int[(int)(N/2)];
			int[] b = new int[(int)(N/2)];
			
			int indA = 0; int indB = 0;
			
			for(int i = 0 ; i < N ; i++){
				if(teamA[i]) {
					a[indA] = i;
					indA++;
				}
				else{
					b[indB] = i;
					indB++;
				}
			}
			
			int ascore = 0 ; int bscore = 0;
			for(int k = 0 ; k <(int)(N/2) ; k++){
				for(int l = 0 ; l < (int)(N/2) ; l++){
					ascore += map[a[k]][a[l]];
					bscore += map[b[k]][b[l]];
				}
			}
			
			return (Math.abs(ascore-bscore));
		}
		else{
			for(int i = idx + 1 ; i < N ; i++){
				if(!teamA[i]){
					teamA[i] = true;
					tmp = DFS(i, N, member + 1);
					if(tmp < min) { min = tmp; }
					teamA[i] = false;
				}
			}
			return min;
		}
	}
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		// initialization
		int N = sc.nextInt();
		map = new int[N][N];
		teamA = new boolean[N];
		
		for(int i = 0 ; i < N ; i++){
			teamA[i] = false;
			for(int j = 0 ; j < N ; j++){
				map[j][i] = sc.nextInt();
			}
		}
		teamA[0] = true;
		//
		int min = Integer.MAX_VALUE;
		min = DFS(0, N, 1);
		
		System.out.println(min);
	}
		
}