[문제 풀이] 백준 14889번 스타트와 링크 JAVA

문제

  문제접근 방법   

해당 문제는 N을 입력받고 NXN의 시너지표? 가 주어질 때 두 팀의 능력치? 시너지가 가장 차이 안 나게 하는 최솟값을 출력하는 프로그램을 작성하는 문제이다.

본 문제는 예전에 어렵게 어렵게 풀어던 기억이 있는데 다시 풀었보니 어렵지만 처음 풀 때보다는 훨씬 쉽게 접근할 수 있었다.

먼저 N명을 두 팀(N/2명) 으로 나누기 위해 DFS 조합으로 팀을 구성하고, 각 팀에서 모든 쌍(i <j)의 시너지 합을 더해 두 팀의 합 차(절댓값)를 최소화한다. 이후 오름차순 인덱스 선택으로 중복 제거, visited 백트래킹으로 모든 조합 탐색하는 방식으로 구현하기로 하였다.

< 최종 코드 >

import java.util.*;

public class Main{
    public static int status[][];
    public static int min=101;
    public static boolean visited[];
    public static ArrayList<Integer> startTeam=new ArrayList<>();
    public static ArrayList<Integer> linkTeam=new ArrayList<>();
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        status=new int[n][n];
        visited=new boolean[n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                status[i][j]=s.nextInt();
            }
            
        }
        dfs(0,0,n/2);
        

        
        System.out.print(min);
    }
    public static void dfs(int start,int depth,int end){
        if(depth==end){
            startTeam=new ArrayList<>();
            linkTeam=new ArrayList<>();
            for (int i = 0; i < visited.length; i++) {
                if (visited[i]) startTeam.add(i);
                else linkTeam.add(i);
            }
            calculate();
            return;
        }

        for(int i=start;i<status[0].length;i++){

            if(!visited[i]){
                visited[i] =true;
                dfs(i+1,depth+1,end);
                visited[i]=false;
            }
        }
     
    }
    public static void calculate(){
        int startSum=0;
        int linkSum=0;
        
        
        for(int i=0;i<startTeam.size();i++){
            for(int j=i+1;j<startTeam.size();j++){
                int a=startTeam.get(i);
                int b=startTeam.get(j);
                int sum=status[a][b]+status[b][a];
                startSum+=sum;
                
            }
        }
        
        for(int i=0;i<linkTeam.size();i++){
            for(int j=i+1;j<linkTeam.size();j++){
                int a=linkTeam.get(i);
                int b=linkTeam.get(j);
                int sum=status[a][b]+status[b][a];
                linkSum+=sum;
            }
        }
        
        int minus=startSum>linkSum?startSum-linkSum:linkSum-startSum;
        min=minus<min?minus:min;
    }
     
}

최종 코드를 간단하게 설명하도록 하겠다. 이 프로그램은 N명의 사람을 두 팀으로 나누어 두 팀의 능력치 차이를 최소화하는 과정을 구현한 프로그램으로 DFS를 통해 N명 중 절반을 선택하여 스타트팀을 구성하고, 선택되지 않은 인원은 링크팀으로 자동 배정하는 방식으로 동작한다. 각 팀의 능력치는 모든 쌍의 조합에 대해 status [a][b] + status [b][a]를 더해 합산하는 구조이며
계산된 두 팀의 능력치 차이는 현재까지의 최솟값과 비교하여 더 작은 값으로 갱신한다.
모든 조합을 탐색한 후, 프로그램은 두 팀의 능력치 차이의 최솟값을 최종적으로 출력한다. 

핵심 로직이라 생각되는 부분은 dfs조합 탐색 메서드와 능력치를 계산하는 calculate 메서드라 생각된다.

  마무리  

해당 문제는 본질적으로 조합 문제라고 보인다. 조합으로 팀을 나누고, 시너지 차이를 계산하는 문제로 조합을 구하는 방법만 알고 있다면 그 이후 로직을 구현하는 것은 어렵지 않다고 생각한다. 만약 조합로직이 미숙하거나 헛갈린다면 n과 m시리즈를 쭉 풀어보는 것을 추천한다.