삼성 SW 역량 테스트 기출 문제 : 스타트와 링크

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

14889번: 스타트와 링크

 

// 코드

import java.util.*;
import java.io.*; 
 
 
public class Main {   
  
  static int N;
  static int[][] arr; 
  static boolean[] visited;
  static int minVal = Integer.MAX_VALUE;
  static boolean flag = false;
  
  
  // main
  public static void main(String[] args) throws Exception{
    
    // Please Enter Your Code Here
    BufferedWriter bw  = new BufferedWriter(new OutputStreamWriter(System.out));
    BufferedReader br  = new BufferedReader(new InputStreamReader(System.in)); 
    
    N = Integer.parseInt(br.readLine());
    arr     = new int[N][];
    visited = new boolean[N];
    for(int i=0; i<N; ++i) arr[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    
    // 재귀를 통해 모든팀을 조합하여 비교한다.
    combi(0, 0);
    bw.write(String.valueOf(minVal));
     
    bw.flush();
    bw.close();
    br.close();
  }
  
  static void combi(int idx, int cnt) {
    
    if(flag) return;
    
    if( cnt == (N/2) ) {
      // 반만 visted가 true 이다.
      getResult();
      return;
    }
    
    for(int i=idx; i<N; ++i) { 
      if(visited[i]) continue;
      visited[i] = true;
      combi(i + 1, cnt+1);
      visited[i] = false; 
    }
  } 
  
  
  // start팀과 link팀을 나누어 최적의 팀조합을 찾아낸다. 
  static void getResult() {
    
    int startTeam = 0, linkTeam = 0;
    
    for(int i=0; i<N-1; ++i) {
      for(int j=i+1; j<N; ++j) {
        // 1. startTeam인 경우
        if(visited[i] && visited[j]) startTeam += (arr[i][j] + arr[j][i]);
        // 2. linkTeam인 경우 
        if(!visited[i] && !visited[j]) linkTeam += (arr[i][j] + arr[j][i]);
      }
    }
    // 0인 경우 flag = true를 해주고 더이상 진행하지 않는다.
    flag = Math.abs(startTeam - linkTeam) == 0 ? true : false;
    minVal = Math.min(minVal, Math.abs(startTeam - linkTeam));
  } 
}