[java] 백준 14889 : 스타트와 링크

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

14889번: 스타트와 링크

 

 

시간초과

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
public class Main {
	static int[][] arr;
	static int n;
	static int min = Integer.MAX_VALUE;
	static boolean[] visited;
    public static void main(String[] args) throws IOException {
    
    	Scanner sc = new Scanner(System.in);
    	n = sc.nextInt();
    	arr = new int[n][n];
    	visited = new boolean[n];
    	for(int i=0; i<n; i++) {
    		for(int j=0; j<n; j++) {
        		arr[i][j] = sc.nextInt();
    		}
    	}
    	
    	combi(0);
    	System.out.println(min);
    	
   
}
    
    static void combi(int count) {
    	if(count == n/2) {
    		diff();
    		return;
    	}
    	for(int i=0; i<n; i++) {
    		if(!visited[i]) {
    			visited[i]= true;
    			combi(count+1);
    			visited[i]= false;
    		}
    	}
    }
    
    static void diff() {
    	int startTeam = 0;
    	int linkTeam = 0;
    	
    	for(int i=0; i<n-1; i++) {
    		for(int j=i+1; j<n; j++) {
    			if(visited[i]==true && visited[j]==true) {
    				startTeam += arr[i][j];
    				startTeam += arr[j][i];
    			}
    			else if(visited[i]==false && visited[j]==false) {
    				linkTeam += arr[i][j];
    				linkTeam += arr[j][i];
    			}
    		}
    	}
    	
    	int diff = Math.abs(startTeam - linkTeam);
    	
    	if(diff ==0) {
    		System.out.println(0);
    		System.exit(0);
    	}
    	
    	min = Math.min(min, diff);
    }
}

 

 

반복문에 인덱스부터 반복문을 돌게 수정

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
public class Main {
	static int[][] arr;
	static int n;
	static int min = Integer.MAX_VALUE;
	static boolean[] visited;
    public static void main(String[] args) throws IOException {
    
    	Scanner sc = new Scanner(System.in);
    	n = sc.nextInt();
    	arr = new int[n][n];
    	visited = new boolean[n];
    	for(int i=0; i<n; i++) {
    		for(int j=0; j<n; j++) {
        		arr[i][j] = sc.nextInt();
    		}
    	}
    	
    	combi(0,0);
    	System.out.println(min);
    	
   
}
    
    static void combi(int idx,int count) {
    	if(count == n/2) {
    		diff();
    		return;
    	}
    	for(int i=idx; i<n; i++) {
    		if(!visited[i]) {
    			visited[i]= true;
    			combi(i+1,count+1);
    			visited[i]= false;
    		}
    	}
    }
    
    static void diff() {
    	int startTeam = 0;
    	int linkTeam = 0;
    	
    	for(int i=0; i<n-1; i++) {
    		for(int j=i+1; j<n; j++) {
    			if(visited[i]==true && visited[j]==true) {
    				startTeam += arr[i][j];
    				startTeam += arr[j][i];
    			}
    			else if(visited[i]==false && visited[j]==false) {
    				linkTeam += arr[i][j];
    				linkTeam += arr[j][i];
    			}
    		}
    	}
    	
    	int diff = Math.abs(startTeam - linkTeam);
    	
    	if(diff ==0) {
    		System.out.println(0);
    		System.exit(0);
    	}
    	
    	min = Math.min(min, diff);
    }
}

 

 

 

참고블로그

https://st-lab.tistory.com/122