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

<문제>

• https://www.acmicpc.net/problem/14889
• 축구를 하기 위해 모인 n명의 사람들(각자 번호 1~n까지 배정)
• 팀을 두팀으로 나눠 진행하는데 능력치의 합이 최소가 되도록 나눔
  • 능력치는 i번 사람과 j번 사람의 Sij Sji의 합으로 두개가 다를 수도 있다

<입력>

• #1: n(4 ≤ n ≤ 20, n은 짝수)
• #2~#n: S(Sii는 항상 0, 1 ≤ Sij ≤ 100)

<출력>

• #1: 두 팀의 능력치 차이의 최솟값

<내 생각>

• 한 팀의 총 능력치를 계산할 때는 팀 내 모든 사람들을 2명씩 묶어 총합으로 계산해야 한다.(ij+ji)
• 총 명수가 6명으로 한 팀씩 3명으로 나눈다고 해도 총 경우의 수는 10이며 심지어 S를 계산하려면 무수히 많은 계산이 필요하다,,
• 문제 특성 상 한명이 팀이 바뀌면 능력치가 바로 바뀌기 때문에 재귀탐색을 통해 한명씩 바꿔보는 것은 맞다
  • 하지만 이 한명씩 바꿔보는 것을 어떤식으로 해야 효율적인가?

  ⇒ 방문배열을 사용한다.

<알고리즘>

• 일단 주어진 S를 이차원배열로 저장
• 방문배열(!!)이 필요
• makeTeam함수:
  • 재귀함수로 팀 조합을 생성(명수가 2/n이 될때까지)
    • 2/n이 되면 getDiff() 함수 호출해서 능력치 차이를 계산하고 최소라면 min 갱신
• getDiff()함수:
  • 이중 for문을 돌면서 ij를 모두 방문했으면 값을 start에 더함
  • ij를 모두 미방문했다면 값을 link에 더함

<전체코드>

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

public class Main {
    static int n; //크기
    static int[][] map; //능력치
    static boolean[] visit; //방문
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        visit = new boolean[n];
        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        makeTeam(0,0); //팀 구성
        System.out.println(min);
    }
    private static void makeTeam(int depth, int start) { //팀 구성(팀 조합)
        if(depth == n/2) {
            min = Math.min(min, getDiff()); //최소값 갱신
            return;
        }
        for(int i=start; i<n; i++) {
            visit[i] = true; //i번째를 팀에 포함
            makeTeam(depth+1, i+1);
            visit[i] = false; //i번째를 팀에서 제외(재귀를 위해)
        }
    }
    private static int getDiff() {
        int start = 0;
        int link = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(i==j) continue;
                if(visit[i] && visit[j]) //ij 모두 방문 시 start 팀
                    start += map[i][j];
                if(!visit[i] && !visit[j]) //ij 모두 미방문 시 link 팀
                    link += map[i][j];
            }
        }
        return Math.abs(start - link); //두 팀의 능력치 차이
    }
}

• 재귀탐색 순서

1. [0, 1] / [2, 3]
2. [0, 2] / [1, 3]
3. [0, 3] / [1, 2]
4. [1, 2] / [0, 3]
5. [1, 3] / [0, 2]
6. [2, 3] / [0, 1]