[BOJ] 14889 스타트와링크 - Java

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

14889번: 스타트와 링크

 

[풀이] 

백트래킹에 조금의 응용이 더 들어간 문제였다. 

1. 일단 조합을 구해야 한다는 점에서 처음 백트래킹을 사용해야겠구나 생각했다.

 

2. 근데 생각해보니까, 총 6명일 때 [1,2,3]조합을 구한다면 [4,5,6]은 자동으로 상대 팀이 된다.

그럼 dfs를 절반만 돌릴 수 있다는거 아닌가? 라는 생각에 일단 6C3값(factorial이라고 써놓음)을 구해서 그 이상이면 컷하게 했다.

 

3. 그리고 팀 구성의 경우 원래 백트래킹은 visit배열을 사용해서 구현한다. 

하지만 여기서 생각해보면 순열이 아니라 조합이므로 순서는 상관없다. 겹쳐도 상관 없다는 뜻이다. 그래서 무조건 index가 커지는 방향으로만 백트래킹을 탐색하도록 했다. (now+1을 통해 구현)

-> 다시 설명하자면

index : 1 => 2,3,4,5,6 다 dfs

index : 2 => 3,4,5,6 dfs

index : 3 => 4,5,6 dfs

index : 4 => 5,6 dfs

index : 5 => 6 dfs

와 같이 해서 index 2인 경우에 다시 1을 탐색하는 경우를 생각하지 않게 작성했다. (앞에서 1,2,X 조합을 봤을텐데 2,1,X 조합을 또 살펴볼 필요는 없기 때문)

 

4. 점수 계산은 팀이 다 구성됐을 때 진행한다.

set을 이용해서 전체에서 조합 구한애들(teamA)을 차집합 연산해서 teamB를 구한다.

 

그리고 잘 생각해보자

조합 [1,2,3]의 능력치 합을 구해야 한다. 그러면 (1,2) / (1,3), (2,3) 의 능력치를 살펴보고 더해줘야 한다.

[1,2,3,4]의 능력치 합을 구해야 한다. 그러면 (1,2) / (1,3), (2,3) / (1,4), (2,4), (3,4) 의 능력치를 살펴보고 더해줘야 한다.

즉 i번째 인덱스의 애가 추가되면 그 밑의 모든 0까지의 능력치를 살펴봐야 한다는 것이다. 

 

* 아 그리고 참고로 어차피 (1,2) 애들을 살펴본다면 1,2/2,1 두 능력치를 다 더해야 하므로 halfMap이라는 것을 만들어서 맵을 반으로 접어 더해놨다.(다 풀고 나니까 쓸데없긴한듯)

 

나머지는 코드로 살펴보자

주석을 잘 달아놨다

 

[코드]

import java.io.*;
import java.util.*;

public class Boj14889_스타트와링크 {
    static StringTokenizer st;
    static int N;
    static int[][] Map;
    static int[][] halfMap;
    static ArrayList<Integer> teamAArr = new ArrayList<>();
    static ArrayList<Integer> AllSet = new ArrayList<>();
    static int total = 0;
    static int answer = Integer.MAX_VALUE;
    static int factorial;

    public static void main(String[] args) throws Exception{
        System.setIn(new FileInputStream("src/main/java/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        Map = new int[N+1][N+1];
        halfMap = new int[N+1][N+1];
        factorial = 1;
        for(int i=N;i>N/2;i--){ //어차피 절반까지만 하면 나머지는 teamA,teamB로 해서 다 볼 수 있으니까 nCm 값 구하기 (ex. 6C3이면 6*5*4/(3*2*1))
            factorial *= i;
            factorial /= (N+1)-i;
        }


        for(int i=1;i<N+1;i++){
            AllSet.add(i);
            st = new StringTokenizer(br.readLine());
            for(int j=1;j<N+1;j++) {
                Map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=1;i<N+1;i++){ //i,j꺼하고 j,i꺼하고 어차피 이 볼거니까 한쪽으로 더해놓기
            for(int j=i+1;j<N+1;j++){
                halfMap[i][j] = Map[i][j] + Map[j][i];
            }
        }

        //START
        for(int i=1;i<N+1;i++){ //1~6까지 돌아가면서 더 큰 애중에 만들 수 있는 조합을 찾을거임
            teamAArr.add(i);
            dfs(i,1);
            teamAArr.remove(teamAArr.size()-1);
        }
        System.out.println(answer);
    }

    static void dfs(int now, int count){
        if(total>factorial/2-1){ //조합의 절반까지 왔으면 그 이상은 안봐도 됨 (어차피 teamA에 속하지 않는애들은 teamB에 속해서, 그 앞의 연산에서 구해줬으므로 중복임)
            return;
        }

        if(count>=N/2){ //N/2명 팀이 구성된 경우
            total++;
            //Arr에 들어있는 애들 sum 하기
            Set<Integer> teamBSet = new HashSet<>(AllSet);
            Set<Integer> set = new HashSet<>(teamAArr);
            teamBSet.removeAll(set); //차집합으로 teamB에 있는 애들 구함
            ArrayList<Integer> teamBArr = new ArrayList<>(teamBSet);

            int sumA = 0, sumB = 0;
            for(int i=1;i<teamAArr.size();i++){ //i는 인덱스라고 생각, i번째 인덱스가 추가됐을 때
                for(int j=i-1;j>=0;j--){ //그 밑의 모든 0까지의 애들과의 스킬을 찾아서 더해야 함
                    sumA += halfMap[teamAArr.get(j)][teamAArr.get(i)]; //teamA꺼는 teamAArr의 j번째 번호인 애랑, i번째 번호인 애꺼를 halfMap(아까 반으로 접어서 합쳐놓은것)에서 찾아야 함
                    sumB += halfMap[teamBArr.get(j)][teamBArr.get(i)];
                }
            }
            answer = Math.min(answer,Math.abs(sumA - sumB));
            return;
        }

        for(int i=now+1;i<N+1;i++){ //지금 나보다 더 큰 인덱스 중에서 가능한 모든 조합 구하기 (now+1~N+1)
            teamAArr.add(i);
            dfs(i,count+1); //dfs고
            teamAArr.remove(teamAArr.size()-1);
        }
    }
}