문제 출처

단계별로 풀어보기 > 백트래킹 > 스타트와 링크
https://www.acmicpc.net/problem/14889

문제 설명

선수 N명이 주어지고, 한 선수 기준으로 다른 선수들과의 시너지가 주어질 때, 스타트와 링크 팀 능력치 차이의 최솟값을 return 하라.

접근 방법

주어진 선수들이 start / link 팀 중 어디에 참여했는지 나타내기 위해 boolean player[], 각 선수끼리의 시너지를 확인하기 위해 int status[][]를 입력받아 생성한다.
한 팀당 선수의 인원은 N/2명 이므로, dfs가 끝나는 조건으로, length(player.length/2)를 설정한다.
그리고, 팀의 인원을 수를 기억하는 depth, 팀이 중복적으로 생기지 않게 index를 설정하여 dfs 내부 for문의 초기 조건을 i = index로 지정한다. i = index로 지정하지 않으면, 중복 조합이 생기기 때문에 지정한다.
만약 depth == length가 되면 permute 메서드를 실행하는데, permute는 player[i], player[j]가 true 이면 start 팀 능력치에 더하고, 반대로 player[i], player[j]가 false이면 link 팀 능력치에 더하는 방식이다.

이렇게 생성된 각 팀의 총합 능력치의 차를 구한 뒤 절대값을 최솟값 Min과 비교한다.
모든 과정이 끝나고 Min을 출력하면 된다.

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

public class 스타트와_링크 {

    public static int status[][];
    public static boolean player[];
    public static int Min = Integer.MAX_VALUE;

    public static int permute(){
        int startSum = 0;
        int linkSum = 0;
        for(int i = 0; i<player.length-1; i++){
            for(int j = i+1; j<player.length; j++){
                if(player[i] && player[j]){
                    startSum += status[i][j];
                    startSum += status[j][i];
                }
                else if(!player[i] && !player[j]){
                    linkSum += status[i][j];
                    linkSum += status[j][i];
                }
            }
        }
        return Math.abs(startSum - linkSum);
    }

    public static void dfs(int depth, int length, int index){
        if(depth == length){
            int result = permute();
            Min = Math.min(result,Min);
            return;
        }

        for(int i =index; i<player.length; i++){
            if(player[i]) continue;
            player[i] = true;
            dfs(depth+1,length,i + 1);
            player[i] = false;
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        player = new boolean[N];
        status = new int[N][N];

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

        dfs(0,N/2, 0);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(String.valueOf(Min));
        bw.flush();
        bw.close();
        br.close();


    }
}

Review

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

public class 스타트와_링크 {

    public static int status[][];
    public static boolean player[];
    public static int Min = Integer.MAX_VALUE;

    public static int permute(){
        int startSum = 0;
        int linkSum = 0;
        for(int i = 0; i<player.length-1; i++){
            for(int j = i+1; j<player.length; j++){
                if(player[i] && player[j]){
                    startSum += status[i][j];
                    startSum += status[j][i];
                }
                else if(!player[i] && !player[j]){
                    linkSum += status[i][j];
                    linkSum += status[j][i];
                }
            }
        }
        return Math.abs(startSum - linkSum);
    }

    public static void dfs(int depth, int length, int index){
        if(depth == length){
            int result = permute();
            Min = Math.min(result,Min);
            return;
        }

        for(int i =index; i<player.length; i++){
            if(player[i]) continue;
            player[i] = true;
            dfs(depth+1,length,i + 1);
            player[i] = false;
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        player = new boolean[N];
        status = new int[N][N];

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

        dfs(0,N/2, 0);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(String.valueOf(Min));
        bw.flush();
        bw.close();
        br.close();


    }
}

알게된 점

풀면서 가장 아쉬웠던 점은 player 배열 자체가 팀을 나눌 수 있는(true/false) 요소 인데, 이를 생각하지 못해서 따로 list로 start/link 팀을 나누려고 했다. 이 과정 때문에 복잡해져서 잘 풀지 못했다.
출처
https://st-lab.tistory.com/122

Review
가장 헷깔렸던 부분은 permute 내부의 j = i+1이다.
이렇게 해야하는 이유는 j = 0으로 하게 되면, 자기 자신과 팀일 때의 시너지가 더해질 수 있다. 이는 결과에 영향을 준다.

문제푼 흔적

Review