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

1. 문제

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

14889번: 스타트와 링크

 

2. 풀이

백트래킹을 이용해 풀이한다.

• DFS를 이용해 한 사람씩 팀에 추가시키고 이를 boolean 배열에 저장한다(boolean[] visited)
• 선택한 사람의 수가 n/2인 경우, 즉 두 팀이 결성된 경우 두 팀의 점수차를 구한다.
• 두 팀의 점수차가 0인 경우 이미 최솟값이므로 프로그램을 종료한다.

 

3. 코드

 

import java.util.*;
import java.io.*;
class Main{
    
    static int n;
    static int[][] abilities;
    static int min = Integer.MAX_VALUE;
    static boolean[] visited;
    
    public static int getScoreGap() {
        int myScore = 0;
        int yourScore = 0;
        
        for(int i = 1; i <= n; i++) {
            for(int j = i+1; j <= n; j++) {
                if(visited[i] && visited[j]) {
                    myScore += abilities[i][j] + abilities[j][i];
                }else if(!visited[i] && !visited[j]) {
                    yourScore += abilities[i][j] + abilities[j][i];
                }
            }
        }
        
        return Math.abs(myScore - yourScore);
    }
    
    public static void backtracking(int idx, int peopleCnt) {
        if(peopleCnt == n/2) { // 한 팀이 완성된 경우
            min = Math.min(min, getScoreGap());
            if(min == 0) { // 0인 경우 더이상 탐색할 필요 없음
                System.out.println(min);
                System.exit(0);
            }
            return;
        }
        
        for(int i = idx + 1; i <= n; i++) {
            visited[i] = true;
           backtracking(i, peopleCnt + 1);
            visited[i] = false;
        }
    }
    
    public static void main (String[] args) throws java.lang.Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        abilities = new int[n+1][n+1];
        visited = new boolean[n+1];
        for(int i = 1; i <= n; i++) {
            String[] input = br.readLine().split(" ");
            for(int j = 1; j <= n; j++) {
                abilities[i][j] = Integer.parseInt(input[j - 1]);
            }
        }
        
       backtracking(0, 0);
        System.out.println(min);
    }
}