[백준] 링크와 스타트 - 백트래킹

1. 문제

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

 

 

2. 접근

2개의 팀을 나누어서 전체 인원을 뽑는다.

스타트 팀에서 N-1명을 뽑았으면, 링크 팀에서는 1명을

스타트 팀에서 N-2명을 뽑았으면, 링크 팀에서는 2명을

...

스타트 팀에서1명을 뽑았으면, 링크 팀에서는 N-1명을

 

엇 근데 경우의 수가 너무 많은 것 같네. 이 방법이 아닌가 보다. 뭐지??? 도저히 모르겠다. 포기

 

접근은 맞았다. 근데 내가 경우의 수가 너무 많다고 생각한 이유는 한 팀을 결정 해놓은 상태에서 다른 팀을 구해야 하는 줄 알아서 AND 연산으로 착각을 했다. 또한 뽑은 인원을 관리할 방법이 생각이 안났다. 하지만 이 문제는 그렇게 푸는 것이 아니었다. 왜냐하면 한 팀에서 인원을 결정하면 자동으로 다른 팀 인원이 결정되기 때문이다. 

 

스타트 팀과 링크 팀의 능력치 차이를 어떻게 구할지를 먼저 잘 생각했으면 좋았을 것 같다.

차이를 구하기 위해서 필요한 것은 `i번째 인원이 속해 있는 팀`의 정보이다. 이 정보만 알면 한 번에 차이를 구할 수 있다. 오히려 중간 중간에 결과를 만들어 낸다고 생각해서 더 어려워진 것 같다. 

 

3. 알고리즘

필요한 로직은 스타트 팀에서 1~N-1명을 뽑은 정보 이다. 스타트 팀을 결정지으면 자동으로 링크 팀이 결정되기에 스타트 팀만 신경 쓰면 된다. N명 중에서 R명을 뽑으면 되니 조합 nCr 을 이용한다.

 

(static 변수를 안쓸려고 해서 매개 변수가 많다)

private void nCr(int depth, int N, int R, boolean[] v,  int [] result,  int [][] friends){
    if(depth == R){
        // 계산
        result[0] = Math.min(result[0], diff(v, friends));

        if(result[0] == 0){
            System.out.println(result[0]);
            System.exit(0);
        }
        return;
    }

    for(int i = depth; i<N; i++){
        // depth가 2여도 4를 뽑았다가 5를 뽑을 수 있음. 그래서 뽑은 여부를 체크해야 함
        if(!v[i]){
            v[i] = true;
            nCr(depth+1, N, R, v, result, friends);
            v[i] = false;
        }
    }
}

 

 

R명의 선수가 모두 뽑혔으면 `diff()`로 차이를 계산한다. 

private int diff(boolean [] v,  int [][] friends){
    int size = v.length;
    int start = 0;
    int link = 0;
    for(int i=0; i<size; i++){
        for(int j=0; j<size; j++){
            if(i == j) continue;
            if(v[i] && v[j]){
                start+=friends[i][j];
            }
            else if(!v[i] && !v[j]){
                link+= friends[i][j];
            }
        }
    }
    return Math.abs(start - link);
}

 

그리고 최소값으로 갱신한다. 

private void nCr(int depth, int N, int R, boolean[] v,  int [] result,  int [][] friends){
    if(depth == R){
        // 계산
        result[0] = Math.min(result[0], diff(v, friends));

        if(result[0] == 0){
            System.out.println(result[0]);
            System.exit(0);
        }
        return;
        
        ...
    }

(갱신하는 과정에서 갱신이 안되는 문제가 있어어서 공부해봤다.)

2025.03.07 - [분류 전체보기] - Java에서 int를 매개변수로 넘길 때 값이 갱신되지 않는 이유

Java에서 int를 매개변수로 넘길 때 값이 갱신되지 않는 이유

 

 

4. 전체 코드

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int run(int N, int [][] friends){
        boolean [] v = new boolean[N];

        int [] ans = new int[1];
        ans[0] = Integer.MAX_VALUE;

        for(int i=1; i<=N-1; i++){
            nCr(0, N, i, v, ans, friends);
        }

        return ans[0];
    }

    private void nCr(int depth, int N, int R, boolean[] v,  int [] result,  int [][] friends){
        if(depth == R){
            // 계산
            result[0] = Math.min(result[0], diff(v, friends));

            if(result[0] == 0){
                System.out.println(result[0]);
                System.exit(0);
            }
            return;
        }

        for(int i = depth; i<N; i++){
            // depth가 2여도 4를 뽑았다가 5를 뽑을 수 있음. 그래서 뽑은 여부를 체크해야 함
            if(!v[i]){
                v[i] = true;
                nCr(depth+1, N, R, v, result, friends);
                v[i] = false;
            }
        }
    }

    private int diff(boolean [] v,  int [][] friends){
        int size = v.length;
        int start = 0;
        int link = 0;
        for(int i=0; i<size; i++){
            for(int j=0; j<size; j++){
                if(i == j) continue;
                if(v[i] && v[j]){
                    start+=friends[i][j];
                }
                else if(!v[i] && !v[j]){
                    link+= friends[i][j];
                }
            }
        }
        return Math.abs(start - link);
    }

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        int [][] friends = new int[N][N];

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

        System.out.println(new Main().run(N, friends));
    }


}