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

14889번: 스타트와 링크 (acmicpc.net)

14889번: 스타트와 링크

 

- n/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 함

- Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해진느 능력

- 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합 

- Sij와 Sji는 다를 수도 있으며 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다 

 

 

- 스타트 팀의 능력치와 링크 팀의 능력치 차이를 최소로 하려고 함 

 

 

문제 풀이 

 

 

[백준/BOJ] 14889번 스타트와 링크 (C/C++) (tistory.com)

[백준/BOJ] 14889번 스타트와 링크 (C/C++)

 

[백준] 14889번 스타트와 링크 - Java, 자바 (velog.io)

[백준] 14889번 스타트와 링크 - Java, 자바

 

- dfs를 활용하여 depth가 n/2가 될 때까지 한 팀으로 구성 

- 모든 조합의 경우의 수를 탐색하여 두 팀의 능력치가 최소가 되는 수를 찾고 이를 출력하면 됨

- 뽑힌 선수를 visited[ ]배열에 저장 (노드의 방문 여부 확인)

- 한 분기가 끝에 도달했을 떄 visited[ ] 내의 true값인 인덱스는 스타트 팀, false값인 인덱스는 링크팀

 

 

정답 

 

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

public class Main {
    static int n;
    static int score[][];
    static boolean visited[];
    
    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());
        
        score = new int[n][n];
        visited = new boolean[n];
        
        for(int i=0; i<n; i++)
        {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++)
            {
                score[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        dfs(0,0);
        System.out.println(min);
    }

    
   static void dfs(int idx, int depth)
   {
       if(depth == n/2)
       {
           diff();
           return;
       }
       
       for(int i=idx; i<n; i++)
       {
           if(!visited[i])
           {
               visited[i] = true; //방문으로 변경
               dfs(i+1,depth+1); //재귀 호출
               visited[i] = false; //재귀가 끝나면 비방문으로 변경
           }
       }
   }
    
   static void diff()
   {
       int start = 0;
       int link = 0;
       
       for(int i=0; i<n-1; i++)
       {
           for(int j=i+1; j<n; j++)
           {
               if(visited[i] == true && visited[j] == true)
               {
                   start +=score[i][j];
                   start +=score[j][i];
               }
               else if(visited[i]==false && visited[j]==false)
               {
            	   link +=score[i][j];
            	   link +=score[j][i];
            	   
               }
           }
       }
       
       int result = Math.abs(start-link);
       
       if(result ==0)
       {
    	   System.out.println(result);
    	   System.exit(0);
       }
       
       min = Math.min(result,min);
   }
    
    
}