백준-14889번/스타트와 링크 (java)

 

문제 접근

 

두 팀의 능력치의 최소 차이를 구하면 된다.

 

인원의 절반은 스타트 팀, 나머지는 링크 팀으로 배치시키는 모든 경우의 수를 구해야 하므로 dfs를 수행해주면 된다.

 

dfs의 종료 조건 :  전체 인원의 절반이 스타트 팀으로 빠졌다면 그 상황에서의 능력치의 차이를 구해주면 된다.

 

 

 문제 풀이

 

N = 인원수

S = 개인 능력치를 저장하는 이차원 배열

visit = dfs에서 방문 유무를 확인할때 쓰이는 일차원 배열

Min = 최소 능력치 차이를 저장

static int N;
static int[][] S;
static boolean[] visit;
static int Min = Integer.MAX_VALUE;

 

 

<dfs 메서드>

idx = 현재 선택된 사원

count =  스타트 팀으로 들어간 인원 수 (절반이 스타트 팀에 들어가면 나머지 절반은 자동으로 링크 팀 이므로 count가 N/2이면 그때의 능력치 차이를 구해주면 된다.) 

static void dfs(int idx, int count){
    if(count==N/2){
        diff();
        return;
    }
    for(int i=idx; i<N; i++){
        if(visit[i]!=true){
            visit[i]=true;
            dfs(i+1,count+1);
            visit[i]=false;
        }
    }
}

 

 

<능력치 차이를 구해주는 메서드 diff>

 

visit[i]와 visit[j]가  true값을 가지면 i번째와 j번째 사원은 스타트 팀에 들어간 것으로 간주 해야 하므로 스타트 팀 능력치 합에 더해준다.

 

링크 팀도 같은 방식으로 더해준다.

 

구해준 두 팀의 능력치의 차이를 최솟값과 비교해준다.

static void diff(){
    int score_start=0;
    int score_link=0;

    for(int i=0; i<N-1; i++){
        for(int j=i+1; j<N; j++){
            if(visit[i]==true && visit[j]==true){
                score_start+=S[i][j];
                score_start+=S[j][i];
            }

            else if(visit[i]==false && visit[j]==false){
                score_link+=S[i][j];
                score_link+=S[j][i];
            }
        }
    }

    int value=Math.abs(score_link-score_start);

    Min=Math.min(value,Min);
}

 

 

<전체 코드>

import java.util.Scanner;


public class Probelm14889 {
    static int N;
    static int[][] S;
    static boolean[] visit;
    static int Min = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N=scanner.nextInt();
        S=new int[N][N];
        visit = new boolean[N];
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                S[i][j]=scanner.nextInt();
            }
        }

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

    }

    static void dfs(int idx, int count){
        if(count==N/2){
            diff();
            return;
        }
        for(int i=idx; i<N; i++){
            if(visit[i]!=true){
                visit[i]=true;
                dfs(i+1,count+1);
                visit[i]=false;
            }
        }
    }

    static void diff(){
        int score_start=0;
        int score_link=0;

        for(int i=0; i<N-1; i++){
            for(int j=i+1; j<N; j++){
                if(visit[i]==true && visit[j]==true){
                    score_start+=S[i][j];
                    score_start+=S[j][i];
                }

                else if(visit[i]==false && visit[j]==false){
                    score_link+=S[i][j];
                    score_link+=S[j][i];
                }
            }
        }

        int value=Math.abs(score_link-score_start);

        Min=Math.min(value,Min);
    }
}