[#알고리즘/DFS&백트래킹/[백준]14889번: 스타트와 링크(java)]

📘 Question

💡 Solution

백트래킹 기법을 이용하여 해결하였다. visited 배열을 이용하여 방문한, 즉 true인 사람들은 스타트팀으로, 방문하지 않은, 즉 false인 사람들은 링크팀으로 구분하였다. dfs()가 N/2만큼 호출되었다면, 한마디로 팀을 다 나눴다면 getScore()에서 시너지를 계산한다. 중요한 점은, 이미 탐색한 사람은 다시 visited를 false로 설정하여 다른 조합을 구성할 수 있도록 한다.

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 BOJ_14889 {
	static int N;
	static int[][] S;
	static boolean[] visited;
	static int min = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		
		S = new int[N][N];
		visited = new boolean[N];
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				S[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		dfs(0, 0);
		System.out.println(min);
	}
	
	public static void dfs(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; j++) {
				// 두 사람이 스타트팀일 경우
				if(visited[i] == true && visited[j] == true) {
					start += S[i][j];
					start += S[j][i];
				}
				// 두 사람이 링크팀일 경우
				if(visited[i] == false && visited[j] == false) {
					link += S[i][j];
					link += S[j][i];
				}
			}
		}
		// 두 팀의 점수 차이 (절댓값)
		int diff = Math.abs(start - link);
		
		// 점수 차가 0이라면 0을 출력 후 프로그램 종료
		if(diff == 0) {
			System.out.println(diff);
			System.exit(0);
		}
		
		min = Math.min(diff, min);
	}

}