<Algorithm> 84. 14889번 스타트와 링크
by BFine반응형
1. 14889번 스타트와 링크
DFS와 백트래킹 문제 , 문제를 이해하는 것이 중요한 것 같다.
13 34 41 하면 같은 팀이 되는 줄 알았는데 그게 아니라 전부 다 해주어야 했다.
백트래킹은 반복문 밖에서 설정 해주어야 한다는 것을 기억하자..
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { public static boolean[] visited; public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br =new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine())+1; int [][] arr = new int[N][N]; visited = new boolean[N]; for(int i = 1; i < N; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); for(int j = 1; j < N;j++) { int c = Integer.parseInt(st.nextToken()); arr[i][j] = c; } } dfs(arr, 0, 0, N); System.out.println(min); } public static void dfs(int[][] arr,int vertax, int dep,int N) { if((N-1)/2 == dep) { total(N, arr); }else { for(int i = vertax + 1; i < N; i++) { if(!visited[i]) { visited[i] = true; dfs(arr,i, dep+1, N); } } } visited[vertax] = false; } public static int min = Integer.MAX_VALUE; public static void total(int N,int[][] arr){ ArrayList<Integer> q1= new ArrayList<Integer>(); ArrayList<Integer> q2= new ArrayList<Integer>(); for(int i = 1; i < N; i++) { if(!visited[i]) { q1.add(i); }else { q2.add(i); } } int total1 = 0; int total2 = 0; for(int i = 0; i<(N-1)/2;i++) { for(int j = 0; j<(N-1)/2;j++) { if(i != j) { total1 += arr[q1.get(i)][q1.get(j)]; total2 += arr[q2.get(i)][q2.get(j)]; } } } if(min > Math.abs(total1-total2)) { min = Math.abs(total1-total2); } } } /*public static void dfs(ArrayList<Node>[] arrayLists,int init,int s, int dep,int total,int N) { if(dep == N/2-1) { for(Node node : arrayLists[s]) { if(node.adj == init) { total += node.weight; } } } visited[s] = true; for(Node node : arrayLists[s]) { if(!visited[node.adj]) { dfs(arrayLists,init,node.adj, dep+1,total+node.weight,N); visited[s]=false; } } } } class Node{ int adj; int weight; public Node(int adj,int weight) { this.adj = adj; this.weight = weight; } }*/ | cs |
참고 & 출처 http://mygumi.tistory.com/243
반응형
'공부(2018~2019) - 스킨변경전 > Algorithm' 카테고리의 다른 글
<Algorithm> 86. 1766번 문제집 (0) | 2018.10.27 |
---|---|
<Algorithm> 85. 15683번 감시 (0) | 2018.10.18 |
<Algorithm> 83. 13458번 시험감독 (0) | 2018.09.24 |
<Algorithm> 82. 3745번 오름세 (0) | 2018.09.12 |
<Algorithm> 81. 1764번 듣보잡 (0) | 2018.09.10 |
블로그의 정보
57개월 BackEnd
BFine