[Baekjoon 14889번/JAVA] 스타트와 링크

Question

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

14889번: 스타트와 링크

 

---

💡 Solution

가장 먼저 팀을 나누기 위해 visited 배열을 이용하여 N명까지 모든 조합을 탐색합니다. 이때 방문한(true) 사람들은 start팀으로, 방문하지 않은(false) 사람들은 link팀으로 구분합니다. 팀을 나눌 때 중요한 점은, 이미 탐색한 사람은 다시 visited를 false로 설정하여 다른 조합을 구성할 수 있도록 합니다.

 

solve가 N / 2만큼 호출되어 팀이 모두 나누어졌다면 getScore() 메서드에서 시너지를 계산 후, 두 팀의 시너지 차이의 최솟값을 구합니다. getScore()에서는 예를 들어 N이 4라면 1 2 / 1 3 / 1 4 / 2 3 / 2 4 ... 이런 식으로 비교를 하게끔 탐색 범위를 설정해주어야 합니다.

 

💻 Code

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

public class BJ14889 {
	static int N;
	static int[][] status;
	static boolean[] visited;
	static int minDiff = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		status = new int[N][N];
		visited = new boolean[N];
		StringTokenizer st;
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				status[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		solve(0, 0);
		System.out.println(minDiff);
	}
	
	/**
	 * N / 2명으로 팀을 나눈다.
	 */
	public static void solve(int num, int count) {
		if (count == N / 2) {
			getScore();
			return;
		}
		
		for (int i = num; i < N; i++) {
			if (!visited[i]) {
				visited[i] = true;
				dfs(i + 1, count + 1);
				visited[i] = false;
			}
		}
	}
	
	/**
	 * 각 팀의 능력치를 구하고, 두 팀의 능력치 차이의 최솟값을 구한다.
	 */
	public static void getScore() {
		int start = 0;
		int link = 0;
		
		for (int i = 0; i < N - 1 ; i++) {
			for (int j = i + 1; j < N; i++) {
				// 두 사람이 스타트팀일 경우
				if (visited[i] == true && visited[j] == true) {
					start += status[i][j];
					start += status[j][i];
				}
				// 두 사람이 링크팀일 경우
				if (visited[i] == false && visited[j] == false) {
					link += status[i][j];
					link += status[j][i];
				}
			}
		}
		
		// 두 팀의 점수 차이(절댓값)
		int diff = Math.abs(start - link);
		
		if (diff == 0) {
			System.out.println(diff);
			System.exit(0);;
		}
		
		minDiff = Math.min(diff, minDiff);
	}

}