[백준] 14889 스타트와 링크 (JAVA)

문제 링크:

14889번: 스타트와 링크

 

 

난이도: 실버 1

 

 

문제:

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

 

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

 

N=4이고, S가 아래와 같은 경우를 살펴보자.

예를 들어, 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보다 작거나 같은 정수이다.

 

출력:

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

 

 

 

문제 이해:

이 문제는 설명이 명확해 이해하기 어렵지 않다.
두 팀으로 나누었을 때, 두 팀의 능력치 차이가 최소가 되는 값을 구하는 것이 목표이다.

첫 줄에는 사람의 수 N이 주어지고,

이후 N × N 행렬이 주어진다. 각 행렬의 원소는 두 사람 간의 능력치를 의미한다.

예를 들어 다음 입력을 보자.

4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0

1번과 2번이 같은 팀일 때의 총 능력치는
S12 + S21 = 1 + 4 = 5 이다.

 

3번과 4번이 같은 팀일 때의 총 능력치는
S34 + S43 = 2 + 5 = 7 이다.

 

따라서 두 팀의 능력치 차이는 |5 - 7| = 2이다.

 

하지만 2번과 3번이 팀을 이루고, 1번과 4번이 한 팀을 이루는 경우에는
양쪽 팀의 능력치 차이가 0이 되어, 이 경우가 정답이 된다.

 

 

구현 방향:

작성자는 문제를 처음 분석할 때, 모든 경우의 수를 탐색해야 한다는 점은 인지했지만,이를 효율적으로 구현하기 위해 백트래킹(Backtracking) 방식을 활용해야 한다는 사실은 처음에는 떠올리지 못했다.

이후 백준 알고리즘 분류를 참고하면서, 이 문제가 백트래킹 유형임을 확인할 수 있었다.

 

구현 방법은 다음과 같다.
모든 가능한 팀 조합을 백트래킹을 통해 탐색하면서,
각 조합이 완성될 때마다 두 팀의 능력치 합을 계산하고,
그 차이를 갱신하며 최소값을 찾아나가면 된다.

 

이를 코드로 구현하면 다음과 같다.

 

 

정답 코드:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static int min=Integer.MAX_VALUE;
    static int [][]matrix;
    static boolean[] visited;
    static int total=0;
    static Stack<Integer> stack= new Stack<>();

    //1팀 능력치  -  2팀 능력치
    public static void calAbility(Stack<Integer> stack) {
        //1팀 능력치 구하기
        int sum = 0;
        int[] arr = new int[stack.size()];

        // 스택의 내용을 배열로 복사
        for (int k = 0; k < stack.size(); k++) {
            arr[k] = stack.get(k);
        }

        // 팀 내 모든 (i, j) 쌍에 대해 능력 합산
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                sum += matrix[arr[i]][arr[j]];
                sum += matrix[arr[j]][arr[i]];
            }
        }

        //2팀 능력치 구하기
        Stack<Integer> st= new Stack<>();
        for (int k = 1; k < N+1; k++) {
            if(!visited[k]) st.add(k);
        }
        int sum1 = 0;
        int[] arr1 = new int[st.size()];

        // 스택의 내용을 배열로 복사
        for (int k = 0; k < st.size(); k++) {
            arr1[k] = st.get(k);
        }

        // 팀 내 모든 (i, j) 쌍에 대해 능력 합산
        for (int i = 0; i < arr1.length; i++) {
            for (int j = i + 1; j < arr1.length; j++) {
                sum1 += matrix[arr1[i]][arr1[j]];
                sum1 += matrix[arr1[j]][arr1[i]];
            }
        }

        //최소값 갱신
        min=Math.min(min,Math.abs(sum1-sum));
    }


    public static void solve(int human,int count){
        //1팀에 포함
        stack.add(human);
        visited[human]=true;

        //팀을 결성 했다면
        if(count==N/2){
            calAbility(stack);
            stack.pop();
            //백트래킹
            visited[human] = false;
            return;
        }

        for (int i=human+1; i<N+1; i++){
            solve(i,count+1);
        }

        //백트래킹
        stack.pop();
        visited[human] = false;
    }

    public static void main(String[] args) throws IOException {
        //초기 세팅
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        N= Integer.parseInt(br.readLine());

        matrix=new int[N+1][N+1];
        visited=new boolean[N+1];

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

        //초기 세팅 끝

        //탐색 시작
        for(int i=1; i<N; i++){
            solve(i,1);
        }

        //결과 출력
        System.out.println(min);


    }
}

 

 

마무리하며:

문제의 이론 자체는 비교적 단순하지만,
실제로 팀의 능력치를 계산하고 재귀적인 탐색 흐름을 구현하는 과정은 쉽지 않았다.
그러나 이를 통해 백트래킹의 개념과 동작 원리를 깊이 이해할 수 있었으며,
백트래킹을 연습하기에 매우 좋은 문제라고 생각한다.

 

 

감사합니다.