문제

BOJ 14889: 스타트와 링크 https://www.acmicpc.net/problem/14889

풀이

• 백트래킹을 사용하여 두 팀에 속할 선수의 번호를 나눠준다.
  • 여기서 A팀은 true, B팀은 false로 구분해준다.
• 백트래킹의 종료 조건 안에서 두 팀의 점수 차이를 구해 가장 작은 값을 출력한다.

코드

import java.io.*;
import java.util.*;
 
public class Main {
	
	static int N;
	static int[][] map;
	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));
 
		N = Integer.parseInt(br.readLine());
 
		map = new int[N][N];
		visit = new boolean[N];
 
 
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
 
		combi(0, 0);
		System.out.println(Min);
 
	}
 
	
	static void bt(int num, int depth) {
		// 팀원 수가 반반이 되면
		if(depth == N/2) {
			diff();
			
			return;
		}
		
		for(int i=num; i<N; i++) {
        	// 방문하지 않았다면
			if(!isChecked[i]) {
				isChecked[i] = true; // 방문 처리
				bt(num + 1, depth + 1); // 재귀 호출
				isChecked[i] = false; // 재귀 끝나면 비방문 처리
			}
			
		}
	}
 
	// 두 팀의 능력치 차이를 계산하는 함수 
	static void diff() {
		int teamA = 0;
		int teamB = 0;
 
		for (int i = 0; i < N - 1; i++) {
			for (int j = i + 1; j < N; j++) {
				// i 번째 사람과 j 번째 사람이 true라면 teamA로 점수 플러스 
				if (visit[i] == true && visit[j] == true) {
					teamA += map[i][j];
					teamA += map[j][i];
				}
				// i 번째 사람과 j 번째 사람이 false라면 teamB로 점수 플러스 
				else if (visit[i] == false && visit[j] == false) {
					teamB += map[i][j];
					teamB += map[j][i];
				}
			}
		}
		// 두 팀의 점수 차이 (절댓값)
		int diff = Math.abs(teamB - teamA);
		
        // 두 팀의 점수 차이가 0이라면 이 때가 최솟값이기 때문에 0을 출력하고 종료한다.
		if (val == 0) {
			System.out.println(diff);
			System.exit(0);
		}
		
		Min = Math.min(diff, Min);
				
	}
 
}

정리

• 각 팀을 true 와 false로 구분할 수 있다는 점을 배웠다.
• 백준 사이트에 제출한 답 중 거의 비슷하지만 시간초과가 나는 코드가 있었다. 다음에 해결해야한다.