[Java] 백준 15661번 링크와 스타트

두 팀으로 팀을 짤 때 각 팀의 시너지의 합의 차가 가장 적은 결과값을 구하는 문제입니다.

한 팀에는 적어도 한명이 있어야 합니다.
비트를 이용해서 visit 처리를 해주었습니다.

팀을 나누고 시너지 값을 각 팀에 더해주고 Math.abs()함수를 사용해서 두 값의 차를 구해주었습니다.
두 값의 차가 가장 적은 결과값을 갱신하여 출력해주었습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	static int ans = 987654321;
	static int n;
	static int[][] map;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		n = Integer.parseInt(br.readLine());
		map = new int[n+1][n+1];
		for(int i=1; i<=n; ++i) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=1; j<=n; ++j) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for(int i=1; i<=n; ++i) {
			DFS(i, 1<<i , 1);
		}
		bw.write(ans + "");
		bw.close();
	}
	public static void DFS(int index, int bit, int cnt) {
		if(cnt > n / 2) {
			return;
		}
		int a = 0;
		int b = 0;
		
		for(int i=1; i<=n; ++i) {
			for(int j=i+1; j<=n; ++j) {
				if((bit & (1<<i)) == 0 && (bit & (1<<j)) == 0) {
					a += map[i][j];
					a += map[j][i];
				} else if ((bit & (1<<i)) != 0 && (bit & (1<<j)) != 0) {
					b += map[i][j];
					b += map[j][i];
				}
			}
		}
		ans = Math.min(ans, Math.abs(a-b));
		for(int i=index+1; i<=n; ++i) {
			DFS(i, bit | 1<<i, cnt + 1);
		}
	}
}