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

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

14889번: 스타트와 링크

풀이

 이 문제를 처음 보았을때는 개인적으로는 실버3 같이 느껴지지 않았다. 나는 처음에 사람들의 집중하기보다는 점수들의 조합에 집중해서 어려웠던것 같다. 

 알고리즘의 개요는 다음과 같다. 모든 사람들의 조합을 구하고 각 조합당 낼수있는 시너지들의 총합을 구하고 이를 스타트와 링크로 나누너 계산해 가장 작은값을 출력하면 된다. 자세한것은 코드를 보면서 이해가 될것이다.

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

class Main{

    public static int N; //입력값 저장
    public static int [][]map; //낼수있는 시너지들을 저장하는 공간
    public static boolean [] visit; //사람들
    public static int Min = Integer.MAX_VALUE; //최소값

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visit = new boolean[N];

        StringTokenizer st;

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0 ; j<N; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        combi(0,0);
        System.out.println(Min);



    }

    public static void combi(int depth, int idx){ //탐을 만들어주는 함수
        if(depth == N/2){
            diff(); // 각 팀원들의 최소값 계산
            return;
        }

        for(int i = idx; i<N; i++){
            if(!visit[i]){
                visit[i] = true;
                combi(depth+ 1 , i + 1); // 팀원이 만들어지지 않았다면 재귀호출로 다시 들어감
                visit[i] = false; // 방문후 미방문으로 처리
            }
        }
    }

    public static void diff(){ // 시너지 차이 계산해주는 함수
        int team_start = 0;
        int team_link = 0;
        for(int i=0; i<N-1; i++){ //i가 N-1일 경우  j는 N가 된다. 이는 아래의 반복문을 들어가도 바로 빠지기 때문에 N-1로 범위 설정
            for(int j=i+1; j<N; j++){ 
               if(visit[i]==true && visit[j]==true){ // 둘다 방문하였을경우 true로 처리
                   team_link += map[i][j];
                   team_link += map[j][i];
               }
               else if(visit[i] == false && visit[j] == false){ // 둘다 미방문시 false로 처리
                   team_start += map[i][j];
                   team_start += map[j][i];
               }
            }
        }
        int val = Math.abs(team_link- team_start); // 시너지 점수의 차이의 절댓값
        if(val == 0){ // 만약 0인 경우 이 이상 시너지 차이가 작아질수없으르모 출력하고 프로그램 종료
            System.out.println(val);
            System.exit(0);
        }

        Min = Math.min(val, Min); // 기존의 최소값과 비교
    }


}