자바(백준) 14889 스타트와 링크

오답 노트 & 새로 알게 된 점

백트래킹 문제를 풀면서 재귀 함수의 인자로 항상 count(depth)로만 설정하여 문제를 풀었다. 그런데 시간 초과가 나와서 앞으로는 start점을 설정해서 돌려야 하겠다는 점을 깨달았다. 

 

풀이 방법

이 문제는 어느 백트래킹 문제와 매우 유사한 문제이다. 단지 애먹었던 부분은 diffSum 부분에서 visit[] 에서 true인 부분들을 어떻게 나열하여 어떻게 arr[][]에 넣어서 더할 수 있을까라는 생각을 했다. 예를 들어 1 2 3이 팀이고, 4 5 6이 팀인데, 여기서 또 2개씩 뽑아서 arr의 index에 넣어 값을 더해야 하는데 여기서 그러면 1 2 3에서 또 숫자를 두 개 뽑아야 하는구나라는 생각이 들었다. 그래서 아 문제가 복잡해지겠구나 했는데, 그냥 처음부터 다시 생각했다. 그래서 그냥 쉽게 해 보자 라는 생각으로 문제를 접근하여 앞에서부터 1 2 / 1 3 / 1 4 / 1 5 / 1 6 이런 식으로 둘 다 true이거나 둘 다 false일 때를 조사하여 start, link팀에 각각 더해주었다.

 

사용 개념

재귀 함수

 

코드

package BackTracking;
 
import java.util.*;
import java.io.*;
 
public class BOJ14889 {
    static int size;
    static int arr[][];
    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));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        size = Integer.parseInt(st.nextToken());
        arr = new int[size][size];
        visit = new boolean[size];
 
        for (int i = 0; i < size; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < size; j++)
                arr[i][j] = Integer.parseInt(st.nextToken());
        }
 
        choiceTeam(0,0);
 
        System.out.print(min);
    }
 
    //팀 뽑기 메소드
    static void choiceTeam(int start, int count){
        if(count == size/2){
            diffSum();
            return;
        }
 
        for(int i = start; i < size; i++){
            if(visit[i]) continue;
            visit[i] = true;
            choiceTeam(i+1,count+1);
            visit[i] = false;
        }
 
    }
 
    static void diffSum(){
        int sum_start = 0, sum_link = 0;
 
        //visit가 true면 start팀, false면 link팀이라 생각
 
        for(int i = 0; i < size - 1; i++){
            for(int j = i+1; j < size; j++){
                if(visit[i] == true && visit[j] == true){
                    sum_start += arr[i][j];
                    sum_start += arr[j][i];
                }
                else if(visit[i] == false && visit[j] == false){
                    sum_link += arr[i][j];
                    sum_link += arr[j][i];
                }
            }
        }
 
        int result = Math.abs(sum_start - sum_link);
 
        if(min > result)
            min = result;
    }
}