전력망을 둘로 나누기

전력망을 둘로 나누기

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);

}

}

from http://zzunsik.tistory.com/210 by ccl(A) rewrite - 2021-10-12 16:01:22