[프로그래머스] [위클리 챌린지 9주차] 전력망을 둘로 나누기 JAVA

[프로그래머스] [위클리 챌린지 9주차] 전력망을 둘로 나누기 JAVA

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

import java.util. * ; import java.io. * ; class Solution { static ArrayList < Integer > [] list; static boolean [] visit; static int [] sub; public int solution( int n, int [][] wires) { list = new ArrayList[n + 1 ]; visit = new boolean [n + 1 ]; sub = new int [n + 1 ]; for ( int i = 1 ;i < = n;i + + ){ list[i] = new ArrayList < > (); } for ( int [] wire : wires) { list[wire[ 0 ]]. add (wire[ 1 ]); list[wire[ 1 ]]. add (wire[ 0 ]); } dfs( 1 , 0 ); int min = Integer.MAX_VALUE; for ( int i = 1 ;i < = n;i + + ){ sub[i] + + ; int diff = Math.abs(n - sub[i] - sub[i]); min = Math.min(min,diff); } // System.out.println("min = " + min); return min; } public static void dfs( int x, int parent){ visit[x] = true ; for (Integer next : list[x]) { if (visit[next]) continue ; dfs(next,x); sub[x] + + ; } sub[parent] + = sub[x]; } } Colored by Color Scripter

from http://katastrophe.tistory.com/47 by ccl(A) rewrite - 2021-10-05 19:00:53