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

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

접근 방법

백트래킹이라고 생각하고 풀었는데 풀고 보니까 DFS인 것 같다.

백트래킹은 DFS와 유사하게 깊이 우선으로 탐색을 하지만 모든 경우를 탐색하는 DFS와는 달리, 유망하지 않으면 탐색하기도 전에 가지치기를 한다는 차이가 있다.

 

먼저, 팀이 나누어지는 모든 경우의 수를 확인하기 위해 DFS를 사용하였다.

 

N명이 있을 때 한 팀당 N/2명으로 동일함으로 한 팀에 N/2명이 채워질 때까지 DFS를 통해 멤버들 번호를 배열에 넣고, 이를 기반으로 상대 팀 멤버 번호 배열을 만들어 준다.

 

팀 배열이 완성되면, 각 팀의 스탯의 합을 구하고 두 팀의 차이를 구해 최솟값과 비교해 반영한다.

 

스탯의 합을 구할 때 주의할 점은 예를 들어 1과 3이 한 팀일 때 stats[1][3]과 stats[3][1]의 스탯이 각각 다르기 때문에 N/2^2 번 탐색해야한다.

 

(이 문제를 오래 전부터 시도해보았는데, 접근 조차 못 했었다. 백트래킹 알고리즘을 익힌 뒤 문제를 접하니 확실히 방향을 잡는데 도움이 되었음을 실감했다. 알고리즘은 많이 풀어보되 무턱대고 덤벼들어서는 안되는 것 같다는 생각이 들었다.)

 

최종 코드

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

public class Main {
    private static int N;
    private static int min = 100;
    private static int[][] stats;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); //선언
        String s = bf.readLine();

        N = Integer.parseInt(s);
        stats = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            String[] input = bf.readLine().split(" ");

            for (int j = 0; j < N; j++) {
                stats[i][j + 1] = Integer.parseInt(input[j]);
            }
        }

        for (int i = 1; i <= N; i++) {
            int[] team = new int[N / 2];
            team[0] = i;
            backtracking(1, team, i);
        }

        System.out.println(min);
    }

    private static void backtracking(int n, int[] team, int depth) {
        if (n == N / 2) {
            int[] otherTeam = setOtherTime(team);

            int total = calculateStats(team);
            int otherTotal = calculateStats(otherTeam);

            int result = Math.abs(total - otherTotal);

            if (result < min) {
                min = result;
            }

        } else {
            depth++;

            for (int i = depth; i <= N; i++) {
                team[n] = i;
                backtracking(n + 1, team, i);
            }
        }
    }

    private static int[] setOtherTime(int[] team) {
        int[] otherTime = new int[team.length];

        int index = 0;

        for (int j = 1; j <= N; j++) {
            boolean isContain = false;

             for (int i = 0; i < team.length; i++) {
               if (j == team[i]) {
                   isContain = true;
               }
            }

            if (!isContain) {
                otherTime[index++] = j;
            }
        }

        return otherTime;
    }

    private static int calculateStats(int[] team) {
        int sum = 0;
        for (int i = 0; i < team.length; i++) {
            for (int j = 0; j < team.length; j++) {
                if (i != j) {
                    sum += stats[team[i]][team[j]];
                }
            }
        }

        return sum;
    }
}