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

https://www.acmicpc.net/problem/2533

2533번: 사회망 서비스(SNS)

문제

풀이

특정 노드 i 번째로 갔다고 가정을하자. 그럼 두 가지의 경우가 나뉘는데 , (얼리아답터를 EA) 

1. i번째가 EA 일 경우 => i의 자식은 EA 이거나 아니다.

2. i번째가 EA 아닐 경우 => i의 자식은 반드시 EA 여야함.

 

문제는 EA의 최소값을 구하는것이 목표이므로 , EA의 최솟값을 나타내는 메모배열을

DP[노드의수][EA] 로 나타낼 수 있다. 따라서 , 점화식은 DFS 방식으로 탐색한다면

dp[i][0] += dp[next][1];

dp[i][1] += Math.min(dp[next][0], dp[next][1]);

으로 표현이 가능하다. 

 

DFS 특성상 가장 깊은데부터 재귀호출이 끝나면 처음지점까지 올라오기때문에 Bottom-UP 방식.이런식으로 올라오면서 채우다보면 맨 처음 Root 노드의 결과 값을 채우게 되면 끝이난다.Root 노드가 ( EA 일때 , EA가 아닐때 ) 값 중 큰 값이 정답.

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