[JAVA] 백준 14889번 : 스타트와 링크 (삼성 SW 역량 테스트 기출 문제)

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

14889번: 스타트와 링크

문제

DFS + 구현 으로 문제를 해결하였다.

 

해결 방안

전체적으로 보면 1. 스타트 팀과 링크 팀 반으로 사람을 나누는 모든 경우의 수와 2. 나눠진 팀의 점수 차이를 구하는 두가지를 구현해야한다.

1. 스타트 팀과 링크 팀 반으로 사람을 나누는 모든 경우의 수는 DFS 탐색을 이용하여 구현하였다.
기저사례가 N/2 일 때까지 DFS 탐색을 하며 N/2 개의 visited를 true로 만들어준다.
caculateDifference()함수에서 visited가 true인 경우는 start 팀에 false인 경우 link 팀에 넣어주었다.

2. 나눠진 팀을 가지고 각 팀의 점수를 getTeamAbility() 함수를 이용하여 구해주었다.
그리고 각각 구해진 팀의 점수를 빼서 절댓값을 구해주었다.

그리고 마지막으로 min인 경우를 찾았다.

 

코드

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

// 스타트와 링크
// 능력치 차이의 최소화
public class Main {

	static int N; // 사람수(4~20, 짝수)
	static int[][] S; // 능력치
	static boolean[] visited;
	
	static int minDifference = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		S = new int[N+1][N+1];
		visited = new boolean[N+1];
		String str;
		StringTokenizer st;
		for(int i=1; i<N+1; i++) {
			str = br.readLine();
			st = new StringTokenizer(str, " ");
			for(int j=1; j<N+1; j++) {
				S[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		// ========= 입력 끝 ==========
		
		dfs(0, 0);
		
		System.out.println(minDifference);
	}
	
	static void dfs(int v, int len) {
		if(len == N/2) {
			// 스타트팀, 링크팀 능력치 차이 구하기
			int difference = caculateDifference();
			// 능력치 차이 최솟값 구하기
			minDifference = Math.min(minDifference, difference);
		}
		else {
			for(int i=v+1; i<N+1; i++) {
				if(!visited[i]) {
					visited[i] = true;
					dfs(i, len+1);
					visited[i] = false;
				}
			}
		}
	}
	
	// 팀 점수 차이 구하기
	static int caculateDifference() {
		
		int[] start = new int[N/2 + 1];
		int[] link = new int[N/2 + 1];
		
		int si = 1; int li = 1;
		for(int i=1; i<N+1; i++) {
			if(visited[i]) start[si++] = i;
			else link[li++] = i;
		}
		
		// 각 팀 점수 구하기
		int startAbility = getTeamAbility(start);
		int linkAbility = getTeamAbility(link);
		
		int difference = Math.abs(startAbility-linkAbility);
		
		return difference;
	}

	// 각팀 점수 구하기
	static int getTeamAbility(int[] team) {
		
		int teamAbility = 0;
		
		for(int i=1; i<team.length; i++) {
			for(int j=i+1; j<team.length; j++) {
				teamAbility += S[team[i]][team[j]];
				teamAbility += S[team[j]][team[i]];
			}
		}
		
		return teamAbility;
	}
}