[BOJ] 14889 스타트와 링크

 

 

[문제]

https://www.acmicpc.net/problem/14889

 

 

[소스 코드]

import java.io.*;
import java.util.*;

public class Main {
	static int n,result;
	static boolean[] visit;
	static int[][] team;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		team = new int[n][n];
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<n;j++) {
				team[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		visit = new boolean[n];
		result = Integer.MAX_VALUE;
		dfs(0,0);
		System.out.println(result);
	}
	private static void dfs(int cnt,int idx) {
		if(cnt==n/2) {
			int link = 0;
			int start = 0;
			for(int i=0;i<n;i++) {
				if(visit[i]) {
					for(int j=0;j<n;j++) {
						if(i!=j && visit[j]) {
							link += team[i][j];
						}
					}
				}
				else {
					for(int j=0;j<n;j++) {
						if(i!=j && !visit[j]) {
							start += team[i][j];
						}
					}
				}
			}
			result = Math.min(result, Math.abs(link - start));
			return;
		}
		for(int i=idx;i<n;i++) {
			if(!visit[i]) {
				visit[i] = true;
				dfs(cnt+1,i+1);
				visit[i] = false;
			}
		}
	}
}