[java]백준 14889번- 스타트와 링크

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

14889번: 스타트와 링크

 

코드

 

package javaCodingTest;

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

public class j14889 {
	static int N;
	static PriorityQueue<Integer> pr;

	static int[][] S;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

		S = new int[N][N];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				S[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		pr = new PriorityQueue<>();//	스타트와 링크 팀의 차이들을 더한 우선순위큐

		ArrayList<Integer> list = new ArrayList<>();
		boolean[] ch = new boolean[N];
		ch[0] = true;

		Select(0, N / 2 - 1, ch);// Team을 스타트와 링크로 나눠주기위한 함수
		System.out.println(pr.poll()); 
	}

	private static void Select(int i, int count, boolean[] check) {
		// i는 i~N까지 숫자를 구하기 위해서 지정! count는 필요한 팀원 수 ,  check는 팀 나누기
		// Team을 스타트와 링크로 나눠주기위한 함수
		if (count == 0) {
			// 팀을 다 구했으면 나눈 팀 별로 S를 더해주고 더해준 값을 우선순위큐에 넣었다.
			pr.add(Sum(check));
			return;

		} else {

			for (int j = i + 1; j < N - count + 1; j++) {
				check[j] = true;
				//재귀를 사용하여 다음 팀원 구하기
				Select(j, count - 1, check);
				check[j] = false;
			}
		}
	}

	private static int Sum(boolean[] check) {
		// 나뉜 팀별로 S 더해주기
		
		ArrayList<Integer> start = new ArrayList<>();  
		ArrayList<Integer> link = new ArrayList<>();
		int s_sum = 0;
		int l_sum = 0;
		for (int i = 0; i < N; i++) {//True면 스타트 False면 링크
			if (check[i] == true) {
				//숫자가 들어올때마다 앞에 팀원들과 개별 S를 더해주기 위해서
				for (int num : start) {
					
					s_sum = s_sum + S[num][i] + S[i][num];
				}
				start.add(i);
			} else {
				for (int num : link) {

					l_sum = l_sum + S[num][i] + S[i][num];
				}
				link.add(i);
			}
		}

		return Math.abs(s_sum - l_sum);

	}
}

 

 

 

풀이

DFS 사용

1. 빈 팀원에 i~N 명중에 재귀와 boolean을 사용하여 팀을 나누어주고. -> Select

2. 팀을 나누고 난 후 팀에 구성원들끼리 차이 계산-> Sum