본문 바로가기

Programmers/Level2

전력망을 둘로 나누기

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
import java.util.*;
class Solution {
    private static int sum = 0;
    public int solution(int n, int[][] wires) {
        int answer = n;
        ArrayList<Node> list = new ArrayList<Node>();
 
        // 노드 생성
        for(int i=0;i<n;i++)
            list.add(new Node(i + 1));
        // 노드 연결
        for(int i=0;i<wires.length;i++){
            Node parent = list.get(wires[i][0- 1);
            Node child = list.get(wires[i][1- 1);
            child.parentAdd(parent);
            parent.childAdd(child);
        }
        // 최소 송전탑 개수 차이 계산
        for(int i=0;i<n;i++){
            Node node = list.get(i);
            
            for(int j=0;j<node.parents.size();j++){
                boolean[] visited = new boolean[n + 1];
                sum = 0;
                visited[node.parents.get(j).number] = true;
                countSet(node, visited);
                answer = Math.min(answer , Math.abs(n - sum * 2));
            }
            for(int j=0;j<node.childs.size();j++){
                boolean[] visited = new boolean[n + 1];
                sum = 0;
                visited[node.childs.get(j).number] = true;
                countSet(node, visited);
                answer = Math.min(answer , Math.abs(n - sum * 2));
            }
        }
        return answer;
    }
    
    public static void countSet(Node node, boolean[] visited){
        if(node == null || visited[node.number])
            return;
        visited[node.number] = true;
        sum++;
        for(int i=0;i<node.parents.size();i++){
            countSet(node.parents.get(i), visited);
        }
        for(int i=0;i<node.childs.size();i++){
            countSet(node.childs.get(i), visited);
        }
    }
}
 
class Node{
    int number;
    ArrayList<Node> parents;
    ArrayList<Node> childs;
    int child_count;
    public Node(int number){
        this.number = number;
        this.child_count = 0;
        this.parents = new ArrayList<Node>();
        this.childs = new ArrayList<Node>();
    }
    public void parentAdd(Node parent){
        this.parents.add(parent);
    }
    public void childAdd(Node child){
        this.childs.add(child);
    }
}
cs

연결된 노드에서 하나씩 끊어가며 경로를 탐색하였다.

'Programmers > Level2' 카테고리의 다른 글

n^2 배열 자르기  (0) 2021.10.25
피로도  (0) 2021.10.25
모음 사전  (0) 2021.10.09
가장 먼 노드  (0) 2021.08.08
행렬 테두리 회전하기  (0) 2021.08.07