스타트와 링크 [백준14889][실버3][Java]

 

[광고 누르면 오늘의 행운 상승!!]

 

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

14889번: 스타트와 링크

조합 + 그래프? 문제

1. visit배열을 이용하여 조합을 구한다.

2. 구해진 2개의 팀의 i,j의 합계를 구한다.

3. 둘을 뺀 절대값의 최솟값을 갱신한다.

package Study0307;

import java.util.*;
import java.io.*;

public class 스타트와링크 {
	
	public static boolean visit[];
	public static int N, ans = Integer.MAX_VALUE;
	public static int[][] map;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		
		map = new int[N][N];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		visit = new boolean[N];
		
		permutation(0, 0);
		System.out.println(ans);
	}
	public static void permutation(int start , int cnt) {
		if(cnt == N/2) {
			int team1=0, team2=0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(i==j) continue;
					if(visit[i] && visit[j]) {
						team1 += map[i][j];
					}else if(!visit[i] && !visit[j]) {
						team2 += map[i][j];
					}
				}
			}
			
			ans = Math.min(ans, Math.abs(team1 - team2));
			return;
		}
		for (int i = start; i < N; i++) {
			if(!visit[i]) {
				visit[i] = true;
				permutation(i, cnt+1);
				visit[i] = false;
			}
		}
	}
}