[백준 14889] 스타트와 링크 (JAVA)

 

 

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

14889번: 스타트와 링크

 

 

생각보다 많이 헤맨 문제였다...

n/2의 선수로 나누는 것으로 모든 선수는 스타트팀과 링크팀으로 무조건 들어간다!!

재귀함수를 통해서 count를 증가시키면서 

방문한 곳은 스타트 팀 소속, 방문하지 않은 곳은 링크 팀 소속으로 배정하여 계산한다!!

 

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

public class Main {
	static boolean[] check;
	static int min=Integer.MAX_VALUE;
	static int t;
	static int[][] arr ;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		t = Integer.parseInt(br.readLine());
		arr = new int[t][t];
		for (int i = 0; i < t; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < t; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		check = new boolean[t];
		check(0,0);
		System.out.println(min);
	}
	
	static void check(int idx,int count) {
		if(count==t/2) {
			cul();
			return;
		}
		for(int i=idx;i<t;i++) {
			if(!check[i]) {
				check[i]=true;
				check(i+1,count+1);
				check[i]=false;
			}
		}
	}
	
	static void cul() {
		int team_start=0;
		int team_link=0;
		
		for(int j=0;j<t-1;j++) {
			for(int z=j+1;z<t;z++) {
				if(check[j]==true&&check[z]==true) {
					team_start+=arr[j][z];
					team_start+=arr[z][j];
				}
				else if(check[j]==false&&check[z]==false) {
					team_link+=arr[j][z];
					team_link+=arr[z][j];
				}
			}
		}

		int diff = Math.abs(team_start-team_link);
		if(diff==0) {
			System.out.println(0);
			System.exit(0);
		}
		
		min = Math.min(min, diff);
		
	}

}