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

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

---

난이도 : 실버3

 

브루트 포스 문제입니다. 

 

주어진 문제의 시간 제한은 2초입니다. 즉 약 2억개의 데이터 안에서 풀 수 있습니다. 

문제의 조건에 따른 최악의 시간복잡도는 (4 ≤ N ≤ 20, N은 짝수)에서 한 데이터를 선택할 수있는 경우와 없는 경우 2가지로 N개를 원소를 가진 배열을 탐색하는 것이므로, 2^20 = 1,048,576. 

충분히 모든 경우를 탐색해도 풀 수 있는 문제입니다. 

 

문제의 대표적인 조건은 각 팀은 N/2의 사람으로 구성되어야 한다는 것입니다. 

주어진 N명 만큼의 모든 사람을 재귀 호출로 탐색하도록 하였고, 탐색한 사람은 전역 변수로 처리한

visit 배열에 true로 저장하였습니다. N/2만큼 호출되면, visit배열의 true인 팀과 false인 팀을 구별하여

각 팀별 능력치를 더한 후, 최솟값을 구했습니다. 

 

그리고 이미 탐색한 사람은 다시 visit 배열에 false로 설정하여 다른 조합을 구성할 수 있도록 하였습니다.

 

- void main()  

모든 전역 변수를 초기화 및 설정해주고 nCr(재귀) 함수를 호출합니다.  

 

- void nCr()

재귀 호출로 N만큼 모든 사람들을 탐색합니다. 호출 횟수가 N/2가 되면 diff()함수를 호출합니다.

 

- void diff()

두 팀의 차이를 구하고 최솟값을 저장합니다.

반복문의 범위에 대해 설명하자면 board의 i==j(대각선)을 기준으로 대칭을 이루기 때문에 board의 i == j (대각선)를 기준으로 오른쪽 부분만 탐색해주면 됩니다.  

 

  코드

public class BOJ_14889 {
	// BOJ / 14889번 / 스타트와 링크 / 브루트포스 / 실3
	static int board[][];
	static int n, min;
	static boolean visit[];
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
        
		n = Integer.parseInt(br.readLine());
		board = new int [n][n];
		visit = new boolean[n];
		min = Integer.MAX_VALUE;
        
		for(int i=0; i<n; i++) {
			stk = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<n; j++) {
				board[i][j] = Integer.parseInt(stk.nextToken());
			}
		}
        
		nCr(0, 0);
        
		System.out.println(min);
	}
	// 재귀 호출로 조합 구현.
	public static void nCr (int start, int depth) {
		
		if(depth == n/2) {
			min = Math.min(min, diff());
			return;
		}
		
		for(int i=start; i<n; i++) {
			if(!visit[i]) {
				visit[i] = true;
				nCr(i+1, depth + 1);
				visit[i] = false;
			}
		}
	}
	// 방문한 팀과 방문하지 않은 팀의 차이를 구한다.
	public static int diff() {
		
		int start = 0;// visit = true 면 start팀
		int link = 0; // visit = false 면 link팀
		
		for(int i =0; i<n-1; i++) {
			for(int j=i+1; j<n; j++) {
				
				if(visit[i] && visit[j]) {
					start += board[i][j] +board[j][i];
				}
                
				else if (!visit[i] && !visit[j]) {
					link += board[i][j] + board[j][i];
				}
			}
		}
		return Math.abs(start - link);
	}
}

 

피드백은 얼마든지 환영합니다.