[백준/JAVA] 14889: 스타트와 링크

[백준/JAVA] 14889: 스타트와 링크

스타트 팀과 링크 팀이 있을 때, 각 팀에 존재하는 선수들끼리의 짝에 따라 팀의 능력치가 증가한다. 이때 두 팀의 능력치 차이를 최소로 만들고자 한다.

백트래킹이 사용되는 부분은 팀을 나누는 케이스를 구하는 부분이다.

1 2 3 4번이 있다면
1 2 / 3 4
1 3 / 2 4
1 4 / 2 3
의 3가지 케이스가 있다.

케이스를 구하는 코드는 15650: N과 M (2) 에서 이미 구한 바 있다.

팀을 절반으로 나눌 뿐이므로 findCase는 인덱스가 n/2가 될때 까지만 반복한다. visited[] = true인 것을 스타트 팀, visited[] = false인 것을 링크 팀이라고 간주하고 for문을 돌며 경우의 수의 최소값을 구한다.

소스코드

---

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

public class Main {
    static int n;
    static int arr[][];
    static int[] team;
    static boolean[] visited;
    static int minResult = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = 
        		new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        
        arr = new int[n][n];
        for (int i = 0; i < n; i++) {
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	for (int j = 0; j < n; j++) {
        		arr[i][j] = Integer.parseInt(st.nextToken());
        	}
        }
        
        /* 두 팀의 능력치 차이를 최소로 하려고 한다.
         * x번과 y번이 같은 팀에 존재할 때 팀의 능력치는 S[x][y]+S[y][x]만큼 증가한다.*/
        team = new int[n];
        visited = new boolean[n];
        findCase(0, 0);
        System.out.println(minResult);
    }
    
    // 팀을 만드는 경우의 수를 찾는다
    public static void findCase(int begin, int idx) {
    	if (idx == n/2) {
    		findMin();
    		return;
    	}
    	for (int i=begin; i<n; i++) {
    		if (!visited[i]) {
    		visited[i] = true;
    		findCase(i+1, idx+1);
    		visited[i] = false;
    		}
    	}
    }
    // min값을 찾는다
    public static void findMin() {
    	int sTeam = 0;
    	int lTeam = 0;
    	for(int i=0; i<n; i++)
    		for (int j=i+1; j<n; j++) {
    		if (visited[i] && visited[j])
    			sTeam += arr[i][j] + arr[j][i];
    		else if (!visited[i] && !visited[j])
    			lTeam += arr[i][j] + arr[j][i];
    		}
    	minResult = Math.min(Math.abs(sTeam-lTeam), minResult);
    }
}