[dfs완탐]백준_스타트링크

무엇가는 완탐으로 선택해주어야 할때는 0,1 방법을 쓴다..

ex) 벽세우기, 팀원고르기,사칙연산 등등 모든경우를 다 따져서 선택하는 경우!!

이 문제의 경우에는 처음부터 완탐이라고 생각해주고 dfs로 접근해주었다. 하지만 모든방향을 접근하지 못하고

한번만 실행되게 되는 경우를 만들고 나머지 팀에대한 함수도 세워서 꽤나 생각을 어렵게 했던 것 같다.

하지만 한 팀을 구하면 나머지 팀원들은 자동을 구해지는 것이기 때문에 한팀을 구하는 것이 중요하다고

생각했다. 한 팀을 구할 때, 처음에는 탐색을 해주면서 능력치 까지 더해 주었기 때문에

i,j를 모두 알아야하는것이 어려웠다.

배열에 팀을 구별해줄수 있게만 팀을 선택해주면 된다고 생각했고

벽세우기와 같은 format으로 해주면 되겠다고 생각했다.

**무작정 배열로 돌리게 되면 시간초과가 발생하는데 이것은 1,2,3 와 3,2,1 은 같은 결과이기 때문이었다.

약간 DP와 같은 개념.. 이미 앞에서는 최적의 값을 계산해주었기 때문에 또 실행할 이유가 없다.

따라서 for문의 시작점을 줄여 주면서 실행을 해주었다.

 

 

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

 

 

 

import java.util.Scanner;
 
public class Main {
    static int N;
    static int[][] map;
    static boolean[] isV;
    static int a,b,c; //뺀 값의 최소 값.
    static int min = Integer.MAX_VALUE;
    
    public static void SelectTeam(int pivot,int len) {
        if(len==N/2) {
            cal(); //팀원 선정이 끝나면 계산 진행.
            return;
        }
        
        for(int i=pivot;i<=N;i++) { //계속 앞방향으로만 진행해준다.
            isV[i]=true;
            SelectTeam(i+1,len+1);
            isV[i]=false;
        }
    }
    
    public static void cal() {
        int teamA=0;
        int teamB=0;
        
        for(int i=1;i<=N;i++) {
            int x = isV[i]==true ? 1 : 0; //팀원을 나누어 주기위해 0,1팀으로 나누어 준다
            for(int j=1;j<=N;j++) {
                int y = isV[j]==true ? 1:0; //2차 맵에서의 값을 매핑하기 위해 각각 다 for문을 이용해준다.
                
                if(x==y && x== 0 ) teamA +=map[i][j]; //같은 팀이면서 0팀인 경우 
                else if (x==y && x==1) teamB +=map[i][j]; //같은 팀이면서 1팀인 경우
            }
        }
        
        min = Math.min(min, Math.abs(teamA-teamB));
    }
    
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new int[N+1][N+1]; 
        isV = new boolean[N+1];
        
        for(int i=1;i<=N;i++) {
            for(int j=1;j<=N;j++) map[i][j]=sc.nextInt();
        }
 
        SelectTeam(1,0);
        System.out.println(min);
    }
}