You will be fine

<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, 00, N);
        System.out.println(min);
    }
    public static void dfs(int[][] arr,int vertax, int dep,int N) {
        if((N-1)/== 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




반응형

블로그의 정보

57개월 BackEnd

BFine

활동하기