백준 백트래킹 - 14889번 : 스타트와 링크

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

14889번: 스타트와 링크

---

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


public class Main {
	static int[][] score;
	static int ans = Integer.MAX_VALUE;
	static int gap = '1'-1;
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		
		score = new int[n][n];
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<n; j++) {
				score[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for(int i=0; i<n; i++) {
			int[] temp = new int[n/2];
			temp[0] = i+1;
			func(n/2,1,temp);
		}
		
		System.out.println(ans);
	}
	static void func(int target,int idx,int[] start) {
		if(idx==target) {
			ans = Math.min(ans,calc(start));
			return;
		}
		for(int i=0; i<score.length; i++) {
			if(i+1<=start[idx-1]) continue;
			start[idx] = i+1;
			func(target,idx+1,start.clone());
		}
	}
	static int calc(int[] nums) {
		ArrayList<Integer> a = new ArrayList<>();
		for(int i=0; i<nums.length; i++) {
			a.add(nums[i]);
		}
		int idx = 0;
		int[] temp = new int[nums.length];
		for(int i=0; i<score.length; i++) {
			if(!a.contains(i+1)) {
				temp[idx++] = i+1;
			}
		}
		int ssum = 0;
		int lsum = 0;
		for(int i=0; i<nums.length; i++) {
			for(int j=i+1; j<nums.length; j++) {
				ssum+=score[nums[i]-1][nums[j]-1];
				ssum+=score[nums[j]-1][nums[i]-1];
				lsum+=score[temp[i]-1][temp[j]-1];
				lsum+=score[temp[j]-1][temp[i]-1];
			}
		}
		return Math.abs(ssum-lsum);
		
	}
}

맨 처음엔 백트래킹 과정에서 중복제거를 위해서 HashSet을 사용했는데 시간초과가 나서 조건 추가로 변경하니 통과되었다 멍청이