사회망 서비스(SNS)

문제

풀이

주어진 그래프에서, 1번 노드는 루트 노드라고 가정합니다.

1번 노드가 가질 수 있는 상태는 다음 두 가지입니다:

1. 얼리 아답터일 때
2. 얼리 아답터가 아닐 때

1. 1번 노드가 얼리 아답터인 경우

이때, 자식 노드들의 상태는 다음 두 가지 중 하나일 수 있습니다:

• 자식 노드가 얼리 아답터일 때
• 자식 노드가 얼리 아답터가 아닐 때

따라서, 이 경우에는 각 자식 노드의 상태별 최소값을 선택하여 더해줍니다:

2. 1번 노드가 얼리 아답터가 아닌 경우

이 경우, 모든 자식 노드는 반드시 얼리 아답터여야 합니다.
따라서, 이 경우에는 각 자식 노드가 얼리 아답터일 때의 값을 전부 더해줍니다:

최종 값

1번 노드의 두 가지 상태에서 계산한 값을 비교하여 최소값을 선택합니다:

이러한 방법으로 모든 노드들을 DP로 계산하면 됩니다.

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    static int N;
    static ArrayList<ArrayList<Integer>> graph;
    static int[][] memo;
    static boolean[] visited;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        graph = new ArrayList();
        memo = new int[N + 1][2];
        visited = new boolean[N + 1];
        
        for (int i = 0; i <= N; i++) {
            ArrayList<Integer> new_list = new ArrayList<>();  
            graph.add(new_list);
        }

        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            ArrayList<Integer> cur_list = graph.get(start);
            cur_list.add(end);

            cur_list = graph.get(end);
            cur_list.add(start);
        }

        for (int i = 0; i <= N; i++) {
            for (int j = 0; j < 2; j++) memo[i][j] = -1;
        }

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

    }

    static int dp (int cur_num, int isAdaptor) {
        if (visited[cur_num]) return 0;
        if(memo[cur_num][isAdaptor] != -1) return memo[cur_num][isAdaptor];
        
        visited[cur_num] = true;
        ArrayList<Integer> new_list = graph.get(cur_num);
        int total = 0;
        
        for (int new_num : new_list) {
            if (isAdaptor == 1) {
                total += Math.min(dp(new_num, 1), dp(new_num, 0));
            }else {
                total += dp(new_num, 1);
            }       
        }
        if (isAdaptor == 1) total += 1;
        
        visited[cur_num] = false;
        memo[cur_num][isAdaptor] = total;
        return total;
    }
}

후기

루트 노드는 항상 1인 줄 알았지만, 아닌 테스트케이스도 존재했습니다.
선택한 노드가 루트노드가 되기 위해선 단반향 그래프가 아닌 양방향 그래프여야 합니다.