https://www.acmicpc.net/problem/14889
public class Main {
static int[][] arr;
static ArrayList<Integer> list;
static int size;
static int MIN;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
size = sc.nextInt();
arr = new int[size + 1][size + 1];
MIN=Integer.MAX_VALUE;
list = new ArrayList<Integer>();
for (int i = 1; i <= size; i++) {
for (int j = 1; j <= size; j++) {
arr[i][j] = sc.nextInt();
}
}
dfs(1);
System.out.println(MIN);
}
private static void dfs(int index) {
if (list.size() == size / 2) {
int[][] visited= new int[size + 1][size + 1];
int result= solve(visited);
if(MIN > result) {
MIN=result;
}
}
for (int i = index; i <= size; i++) {
list.add(i);
dfs(i + 1);
list.remove(list.size() - 1);
}
}
private static int solve(int[][]arr2) {
int startteam=0;
int linkteam=0;
for(int i=0;i<list.size();i++) {
int number=list.get(i);
for(int j=1;j<=size;j++) {
if(number==j) {
arr2[number][j]=0;
}
else {
arr2[number][j]++;
}
}
for(int k=1;k<=size;k++) {
if(number==k) {
arr2[k][number]=0;
}
else {
arr2[k][number]++;
}
}
}
for(int i=1;i<=size;i++) {
for(int j=1;j<=size;j++) {
if(i==j) {
continue;
}
if(arr2[i][j]==2) {
startteam=startteam+arr[i][j];
continue;
}
if(arr2[i][j]==0) {
linkteam = linkteam+arr[i][j];
}
}
}
int result= Math.abs(startteam-linkteam);
return result;
}
}
'코딩테스트(백준)' 카테고리의 다른 글
[백준] 14502 : 연구소 - JAVA(자바) - 사좋배 공유 (0) | 2020.07.27 |
---|---|
[백준] 16236 : 아기 상어 - JAVA(자바) - 사좋배 공유 (0) | 2020.07.27 |
[백준] 17144: 미세먼지 안녕! - JAVA(자바) - 사좋배 공유 (0) | 2020.07.27 |
[백준] 14503 : 로봇 청소기 - JAVA(자바) - 사좋배 공유 (0) | 2020.07.27 |
[백준] 15683 : 감시 - JAVA(자바) - 사좋배 공유 (0) | 2020.07.27 |