[BOJ] 백준 [2533] 사회망 서비스(SNS) JAVA

[BOJ] 백준 [2533] 사회망 서비스(SNS) JAVA

import java.util. * ;

import java.io. * ;

import java.util.stream.Collectors;

public class Main{

static ArrayList < Integer > [] list;

static int [][] dp;

public static void main( String [] args) throws IOException {

BufferedReader br = new BufferedReader( new InputStreamReader( System . in ));

int N = Integer. parseInt (br.readLine());

list = new ArrayList[N + 1 ];

dp = new int [N + 1 ][ 2 ];

for ( int i = 1 ;i < = N;i + + )

list[i] = new ArrayList < Integer > ();

for ( int i = 1 ;i < N;i + + ){

int [] e = Arrays.stream(br.readLine(). split ( " " )).mapToInt(Integer:: parseInt ).toArray();

list[e[ 0 ]]. add (e[ 1 ]);

list[e[ 1 ]]. add (e[ 0 ]);

}

dfs( 0 , 1 );

System . out . println (Math.min(dp[ 1 ][ 0 ],dp[ 1 ][ 1 ]));

}

public static void dfs( int parent, int x){

dp[x][ 0 ] = 0 ;

dp[x][ 1 ] = 1 ;

for ( int node : list[x]) {

if (node = = parent)

continue ;

dfs(x,node);

dp[x][ 0 ] + = dp[node][ 1 ];

dp[x][ 1 ] + = Math.min(dp[node][ 0 ], dp[node][ 1 ]);

}

}

}

from http://katastrophe.tistory.com/44 by ccl(A) rewrite - 2021-09-30 15:27:22