[BOJ] 14889. 스타트와 링크 - JAVA

🔗 문제

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

14889번: 스타트와 링크

 

💻 풀이 및 코드

문제 유형 : 브루트포스, 백트랙킹

 

인원을 두 그룹으로 나누어 두 그룹 간의 실력 차가 가장 적은 그룹 조합을 구하는 문제

 

전체 코드

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

public class Main_bj_14889_스타트와링크 {
	
	static int N, ans = Integer.MAX_VALUE;
	static int[][] graph;

	public static void main(String[] args) throws Exception {
//		System.setIn(new FileInputStream("res/input_bj_14889.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		graph = new int[N][N];
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<N; j++) {
				graph[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		backTracking(0, 0, new boolean[N]);
		
		System.out.println(ans);
		br.close();
	}
	
	static void backTracking(int cnt, int choice, boolean[] groupA) {
		if(cnt >= N || choice > N/2) return;
		
		if(choice == N/2) {
			int a=0,b=0;
			
			for(int i=0; i<N; i++) {
				if(groupA[i]) {
					for(int j=i+1; j<N; j++) {
						if(groupA[j]) {
							a += graph[i][j] + graph[j][i];
						}
					}
				} else {
					for(int j=i+1; j<N; j++) {
						if(!groupA[j]) {
							b += graph[i][j] + graph[j][i];
						}
					}
				}
			}
			
			ans = Math.min(ans, Math.abs(a-b));
			return;
		}
		
		groupA[cnt] = true;
		backTracking(cnt+1, choice+1, groupA);
		groupA[cnt] = false;
		backTracking(cnt+1, choice, groupA);
		
	}

}