[백준] 14889번 스타트와 링크 with 백트래킹 method : Programming Story

www.acmicpc.net/problem/14889

문제

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

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

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

입력

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

출력

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

문제의 자세한 조건은 위 링크로 들어가서 확인해보자!!

우선 알고리즘을 설명하기 전에 백트래킹 (Backtracking) 이라는 것은 무엇일까?

재귀함수를 이용해 브루트 포스를 하다 보면, 더 이상 함수 호출이 의미가 없는 경우가 있다.
브루트 포스는 가능한 모든 경우를 다 시도해보는 것인데, 이러한 의미 없는 경우를 제외하고 브루트포스를 진행하는 방법을 백트래킹이라고 하는 것이다. 백트래킹을 하면 시간을 많이 단축시킬 수 있다는 장점이 있다.

이 문제의 경우 사람을 첫번째 팀과 두 번째 팀으로 각각 나누어, 두 팀의 능력치를 구한 다음, 차이의 최소값을 구하는 문제이다.

즉 각 팀에 n/2명이 골고루 들어가 있어야 하는데, 이 문제는 한명 한명을 각 팀에 넣어보는 식으로 문제를 풀어볼 것이다.

한 사람을 첫 번째 팀에다가도 넣어보고 두 번째 팀에다가도 넣어보고 모든 경우를 다 해보게 되면 이는 브루트 포스이지만, 여기서 굳이 하지 않아도 되는 경우가 있다.

바로 한명씩 넣다가 한 팀의 명수가 n/2를 초과하는 경우에는 팀 결성이 균등하게 되어 버린것이 아니기 때문에 굳이 차이를 계산할 필요가 없다. 따라서 한 팀의 명수가 n/2를 초과하는 경우 바로 return 해버리는 것이 시간 단축의 핵심이다.

이것도 재귀와 방법은 비슷하기 때문에 크게 세 가지의 경우의 수로 나누어서 생각해볼 수 있다.

재귀 함수의 원형은 go(index, first, second)이다

index: index 번째 사람을 어느 팀에 넣을지 결정

first: 1번째 팀의 사람의 arraylist

second: 2번째 팀의 사람의 arraylist

정답을 찾은 경우:

index==n 일때 !!

이 경우에도 각각의 팀의 명수가 n/2로 균등하게 잘 배분되었는지 확인하는 추가절차가 필요하다.
그리고 나서 두 팀의 역량의 합의 차이를 return 하는 코드가 추가되어야 한다.

 if (index==n){
            if (first.size()!=n/2) return -1;
            if (second.size()!=n/2) return -1;
            int a1=0;
            int a2=0;
            for(int i=0; i<n/2; i++){
                for(int j=0; j<n/2; j++){
                    if (i==j) continue;
                     a1 += s[first.get(i)][first.get(j)];
                    a2 += s[second.get(i)][second.get(j)];
                }
            }
             int diff = Math.abs(a1-a2);
            return diff;
        }

불가능한 경우:

first의 크기 > n/2
second의 크기 >n/2

다음의 경우:

- 먼저 first에 해당 index를 넣어준다.
- go(index, first, second)
- 다음 first에 index를 제거해준다

-second arraylist도 마찬가지 과정을 거친다

이렇게 세 가지 경우를 고려하고 나면,

import java.util.*;

public class Main{
    static int s[][];
    static int n;
    static int go(int index, ArrayList<Integer> first, ArrayList<Integer> second){
        if (index==n){
            if (first.size()!=n/2) return -1;
            if (second.size()!=n/2) return -1;
            int a1=0;
            int a2=0;
            for(int i=0; i<n/2; i++){
                for(int j=0; j<n/2; j++){
                    if (i==j) continue;
                     a1 += s[first.get(i)][first.get(j)];
                    a2 += s[second.get(i)][second.get(j)];
                }
            }
             int diff = Math.abs(a1-a2);
            return diff;
        }
        if (first.size() > n/2) return -1;
        if (second.size() > n/2) return -1;
        int ans = -1;
        first.add(index);
        int t1 = go(index+1, first, second);
        if (ans == -1 || (t1 != -1 && ans > t1)) {
            ans = t1;
        }
        first.remove(first.size()-1);
        second.add(index);
        int t2 = go(index+1, first, second);
        if (ans == -1 || (t2 != -1 && ans > t2)) {
            ans = t2;
        }
        second.remove(second.size()-1);
        return ans;
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
         n=sc.nextInt();
         s=new int[n][n];
         for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                s[i][j] = sc.nextInt();
            }
        }
        ArrayList<Integer> first=new ArrayList<>();
        ArrayList<Integer> second=new ArrayList<>();
        System.out.println(go(0, first, second));
    }
}

다음과 같은 코드로 완성할 수 있다.

여기서 백트래킹의 핵심이 되는 코드는 다음의 코드라고 할 수 있다.

        if (first.size() > n/2) return -1;
        if (second.size() > n/2) return -1;

참고로 이 문제는 1번팀에 넣냐, 2번팀에 넣냐로 생각하여 비트마스크로 해결할 수도 있는데,

https://www.programmingstory.com/2024/02/1285.html

비트마스크로 푼 알고리즘이 궁금하다면 위의 링크를 클릭해보면 된다.