백준 14889번 : 스타트와 링크 java

이 문제는 백트래킹 파트 안에 있는 깊이 우선 탐색(dfs)을 이용하여 푸는 문제입니다.

이 문제를 풀 때 유의해야 하는 점은 N이 6이라고 할 때 1 2 3이 한 팀이고 4 5 6이 한 팀일 때
1->2, 2->1로 받는 능력치 1->3, 3->1로 받는 능력치 2->3, 3->2로 받는 능력치
이렇게 안에 포함된 모든 팀원들의 능력치 합을 더해서 구해주어야 된다는 겁니다.

코드를 보면서 추가로 설명드리도록 하겠습니다.

---

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

public class Main{
    static int[][] stat;
    static int minNum = Integer.MAX_VALUE;
    static boolean[] visited;
    static int N;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        stat = new int[N][N];
        visited = new boolean[N];

        for(int i = 0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            for(int j = 0; j<N; j++)
                stat[i][j] = Integer.parseInt(st.nextToken());
        }

        find(0, 0);

        System.out.println(minNum);
    }

    static void find(int depth, int count){
        if(count == N/2){
            int aTeamSum = 0;
            int bTeamSum = 0;

            for(int i = 0; i<N-1; i++){
                for(int j = i+1; j<N; j++){
                    if(visited[i] && visited[j]) {
                        aTeamSum += stat[i][j];
                        aTeamSum += stat[j][i];
                    }
                    if(!visited[i] && !visited[j]) {
                        bTeamSum += stat[i][j];
                        bTeamSum += stat[j][i];
                    }
                }
            }

            int val = Math.abs(aTeamSum - bTeamSum);

            if(val == 0) {
                System.out.println(val);
                System.exit(0);
            }
            minNum = Math.min(minNum, val);
            return;
        }

        for(int i = depth; i<N; i++) {
            if(!visited[i]) {
                visited[i] = true;
                find(i + 1, count + 1);
                visited[i] = false;
            }
        }
    }
}

이 문제는 반복을 좀 더 많이 돌 경우 시간초과가 많이 나옵니다. 그래서 반복문의 초기 식이나 종료 조건을 조금 더 세심히 설정해주셔야 합니다.

우선 저는 stat에 각각 팀이 될 때 받는 능력치를 넣었고, visited를 통해서 팀이 되는 사람들을 나누었습니다.
visited[i]가 true인 사람들이 한 팀이고 visited[i]가 false인 사람들이 또 한 팀을 이룹니다.

find함수의 종료 조선은 count가 N/2가 될 때입니다. 이 때 count는 팀원이 몇 명이냐를 세어준 것입니다.

종료 조건 내에서 j를 변수로 선언한 두 번째 반복문에서 초기 식이 j = i+1인 이유는

if(visited[i] && visited[j]) {
    aTeamSum += stat[i][j];
    aTeamSum += stat[j][i];
}

이런 식으로 2명이 같은 팀일 때 서로 영향을 받는 능력치를 한번에 더해주기 때문에 i 이전에 있는 것들을 한번 더
더해줄 이유가 없기 때문입니다.

val이 0일 때 프로그램을 바로 종료시켜주는 이유는 이 문제의 목표가 각 팀의 능력치의 합의 차이가 가장 작을 때를
구하는 것인데 0 밑으로는 차이가 내려갈 수 없기 때문에 의미없이 연산을 더 하는 것을 방지하기 위해서입니다.