[백준] 14889 스타트와 링크

 

 

---

https://st-lab.tistory.com/122

[백준] 14889번 : 스타트와 링크 - JAVA [자바]

 

 

---

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

public class Main {
	static int Min = 100;
	static int N;
	static int xy[][];
	static boolean visit[];
	public static void main(String[] args)throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		xy = 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++) {
				xy[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		//4개일 때 2개가 되면
		dfs(0,0);
		System.out.println(Min);
	}
	static void dfs(int idx, int deepth) {
		if(N/2 == deepth) {
			team();
			return;
		}
		for(int i = idx; i < N; i++) { //1-2 1-3 1-4 2-3 2-4 3-4만 찾기
			if(!visit[i]) { //N이 6 이상일 때부터 팀을 구별해준다
				visit[i] = true;
				dfs(i + 1,deepth + 1); //idx + 1도 답이 나오긴 하나 시간초과 i + 1로 하면 1 3을 조사할 때 4 5만 조사하나
				//idx + 1로 하면 1 3을 조사할 때 2 4 5를 조사한다. N이 커지면서 이 값도 무지막지하게 커져서 시간초과가 나왔다
				visit[i] = false;
			}
		}
	}
	static void team() {
		int start_team = 0;
		int link_team = 0;
		for(int i = 0; i < N-1; i++) { //12 13 14 23 24 34
			for(int j = i+1; j < N; j++) {
				if(visit[i] == true && visit[j] == true) { //136 = 13 16 36 31 61 63
					start_team += xy[i][j] + xy[j][i];
				}
				else if(visit[i] == false && visit[j] == false) {
					link_team += xy[i][j] + xy[j][i];
				}
			}
		}
		int result = Math.abs(link_team-start_team);
		Min = Math.min(Min, result);
	}
}