[백준 14889] 스타트와 링크(JAVA)

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

14889번: 스타트와 링크

 

먼저 문제 해석을 하자면

 

n명의 사람을 두 팀으로 나눌 때 두팀의 능력치 차이가 제일 적은 경우에 대해 그 차를 출력하면 되는 문제이다.

 

각 인원은 서로 팀이 되는 경우마다 능력치가 바뀌기 때문에 각 인원에 대해 갖는 능력치를 행렬로 입력 받는다.

 

즉 i와 j가 팀인 경우 (i,j) + (j,i) 가 팀의 능력치로 계산된다.

 

모든 경우의 수를 구하고 각 경우의 수중에서 최소값을 찾는 문제이기 때문에 브루트포스로 접근하되

 

이때 입력을 행렬로 받고 전체인원을 둘로 나누는 경우의 수를 구하는것이기 때문에 백트래킹을 통한 풀이가 

가능하다.

 

깊이를 n/2 만큼 진행하는 재귀로 구현해서 풀면 되기 때문이다.

 

 

우선 static 자원으로 전체 인원수 n, 그리고 최소값 저장할 변수 min , 그리고 입력받을 행렬 저장할 배열,

팀을 구분할 배열을 선언 해주겠다.

 

	static int n;
	static int min = Integer.MAX_VALUE;
	
	static int[][] metrix;
	static boolean[] visit;

 

 

다음은 백트래킹을 통해 팀을 구분할 메소드를 만들도록 하겠다.

 

	static void pro(int idx, int cnt) {
		if(cnt == n/2) {
			min = Math.min(min, 현재 나눈 팀에 대해 차이를 구할 함수);
			return;
		}
	}

 

먼저 재귀의 탈출 조건은 팀이 둘로 나뉘었을 경우이기 때문에 재귀 호출시마다 인자로 주어 증가시킬 cnt가 

현재 n의 반에 해당한다면 리턴 해줄 수 있도록 만들었다.

 

이 때 최소값을 갱신시켜주어야 하므로 아직 생성하지 않은 임의의 함수를 넣어줄 자리를 만들었다.

 

이어서 가자면 이제 남은 건 순회하면서 방문처리와 재귀호출을 반복해주면 된다. 

 

	static void pro(int idx, int cnt) {
		if(cnt == n/2) {
			min = Math.min(min, . . .);
			return;
		}
		for(int i = idx; i < n; i++) {
			visit[i] = true;
			pro(i + 1, cnt + 1);
			visit[i] = false;
		}
	}

 

중복을 막기 위해서 인자로 반복문의 시작점을 잡고 재귀 호출전 방문처리, 호출후 초기화를 반복해준다.

 

 

이제 팀을 둘로 나누는 과정은 완성이 되었으니

둘로 나눈 팀의 차이를 구하는 메소드를 작성해보도록 하겠다.

 

현재 팀의 구분을 visit 배열에서 true , false로 구분했으므로

두명씩 선택하되 둘다 true 이거나 false 이거나로 구분해 차이를 구해주면 된다.

 

	static int getGap() {
		int temp = 0;
		for(int i = 0; i < n; i++) {
			for(int j = i + 1; j < n; j++) {
				if(visit[i] && visit[j]) {
					temp += metrix[i][j] + metrix[j][i];
				}else if(!visit[i] && !visit[j]) {
					temp -= metrix[i][j] + metrix[j][i];
				}
			}
		}
		return Math.abs(temp);
	}

 

임의의 변수 temp에 둘다 true일땐 더하고 둘다 false일땐 빼준 뒤

절댓값을 사용, 양수로 만들어준뒤 리턴해주도록 했다.

 

이제 이전에 만든 백트래킹 함수에 방금 만들어준 차이구해주는 함수를 넣어주기만하면 

백트래킹을 통해 최소차이를 구해줄수 있다.

 

 

 

 

예제에 대한 출력이다.

 

정확히 나오는 것을 확인할수 있다.

 

아래는 코드의 전문이다.

 

package boj3;

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

public class Boj14889 {
	
	/*
	 * 제출 完
	 */
	
	static int n;
	static int min = Integer.MAX_VALUE;
	
	static int[][] metrix;
	static boolean[] visit;
	
	static int getGap() {
		int temp = 0;
		for(int i = 0; i < n; i++) {
			for(int j = i + 1; j < n; j++) {
				if(visit[i] && visit[j]) {
					temp += metrix[i][j] + metrix[j][i];
				}else if(!visit[i] && !visit[j]) {
					temp -= metrix[i][j] + metrix[j][i];
				}
			}
		}
		return Math.abs(temp);
	}
	
	static void pro(int idx, int cnt) {
		if(cnt == n/2) {
			min = Math.min(min, getGap());
			return;
		}
		for(int i = idx; i < n; i++) {
			visit[i] = true;
			pro(i + 1, cnt + 1);
			visit[i] = false;
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(in.readLine());
		metrix = new int[n][n];
		visit = new boolean[n];
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(in.readLine()," ");
			for(int j = 0; j < n; j++) {
				metrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		in.close();
		
		pro(0,0);
		
		System.out.print(min);
		
	}

}