구현

백준 14889번 구현 문제를 백트래킹을 이용해 Java로 풀어보았다.
골드 문제들을 연달아 실패하는 가운데 다 부수고 싶어서 실버 한 문제 풀고 잠시나마 가짜 성취감을 만끽 중이다.

문제 링크만 첨부하겠다.
https://www.acmicpc.net/problem/14889

---

백트래킹

앞서 풀어봤던 15686번과 같은 원리로 풀 수 있다. 조건에 맞지 않는 녀석은 넘기고 조건에 맞는 놈만 재귀방식으로 추가해서 팀 하나를 맞추면 된다.

static void BackTracking(int idx, int cnt){
        if(cnt==n/2){ // 팀 하나 구성할 사람을 모았으면 여기로
            team1.clear();  team2.clear();
            MakeTeams(); // 두 팀 모두 완성
            int team1_cap = 0;  int team2_cap = 0;
            team1_cap = GetTeamCap(team1);  team2_cap = GetTeamCap(team2);
            int gap = Math.abs(team1_cap - team2_cap);
            if(gap<min) min = gap;
        }
        else{
            for(int i=idx; i<n; i++){
                if(!visited[i]){ // 조건에 맞는 놈만 추가하자
                    visited[i] = true;
                    BackTracking(i+1, cnt+1);
                    visited[i] = false;
                }
            }
        }
    }

그렇다면 위에서 몇 번 idx의 선수들을 모을지 결정한 거니까 위의 visited 정보를 가지고 실제 팀을 만들 코드는 아래와 같이 작성하면 된다.

static void MakeTeams(){
        for(int i=0; i<n; i++){
            if(visited[i])    team1.add(i);
            else    team2.add(i);
        }
    }

딱 두 팀을 만들 거기 때문에, 방문한 선수들끼리 그리고 방문하지 않은 선수들끼리 팀을 만들면 된다.

---

각 팀의 능력치 구하기

각 팀을 LinkedList로 각 선수의 index를 넣어뒀다. 딱 두 명끼리의 능력치들을 합산해주면 되기 때문에 이중 for문을 통해 가능한 모든 선수의 조합을 찾아줄 수 있다.

static Integer GetTeamCap(LinkedList<Integer> t){
        int cap = 0;
        for(int i=0; i<t.size()-1; i++){
            for(int j=i+1; j<t.size(); j++){
                cap += (level[t.get(i)][t.get(j)] + level[t.get(j)][t.get(i)]);
            }
        }
        return cap;
    }

이렇게 각 팀의 능력치를 구해서 BackTracking(int idx, int cnt) 메소드에서 두 팀의 능력차를 매번 계산해서 최솟값을 갱신해주어 마지막에 남는 값을 출력해주면 된다.

아래는 내가 제출한 코드다.

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

public class boj14889 {
    static int n;
    static int min = Integer.MAX_VALUE;
    static int[][] level;
    static boolean[] visited;
    static LinkedList<Integer> team1 = new LinkedList<>(), team2 = new LinkedList<>();

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk = new StringTokenizer(bfr.readLine());
        n = Integer.parseInt(stk.nextToken());
        level = new int[n][n];  visited = new boolean[n];
        for(int i=0; i<n; i++){
            stk = new StringTokenizer(bfr.readLine());
            for(int j=0; j<n; j++)
                level[i][j] = Integer.parseInt(stk.nextToken());
        }

        BackTracking(0,0);
        bfw.write(String.valueOf(min));
        bfw.close();
    }

    static void BackTracking(int idx, int cnt){
        if(cnt==n/2){
            team1.clear();  team2.clear();
            MakeTeams(); // 두 팀 모두 완성
            int team1_cap = 0;  int team2_cap = 0;
            team1_cap = GetTeamCap(team1);  team2_cap = GetTeamCap(team2);
            int gap = Math.abs(team1_cap - team2_cap);
            if(gap<min) min = gap;
        }
        else{
            for(int i=idx; i<n; i++){
                if(!visited[i]){
                    visited[i] = true;
                    BackTracking(i+1, cnt+1);
                    visited[i] = false;
                }
            }
        }
    }

    static void MakeTeams(){
        for(int i=0; i<n; i++){
            if(visited[i])    team1.add(i);
            else    team2.add(i);
        }
    }

    static Integer GetTeamCap(LinkedList<Integer> t){
        int cap = 0;
        for(int i=0; i<t.size()-1; i++){
            for(int j=i+1; j<t.size(); j++){
                cap += (level[t.get(i)][t.get(j)] + level[t.get(j)][t.get(i)]);
            }
        }
        return cap;
    }
}

오늘 배운 것

골드는 어렵다. 나는 실딱이다. 실발