자바 - 백준 2533 / 사회망 서비스(SNS)

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

골드3

구현 방법

• 문제 조건에서 “친구 관계가 트리 구조”라고 했기 때문에 사이클이 없고, 모든 노드가 연결되어 있습니다.
  • 따라서 DFS나 재귀를 통해 트리 순회가 가능해집니다.
• 상태는 2가지로 나뉩니다.
  • 얼리어답터인 경우 : 자신의 친구는 얼리어답터가 아니여도 됩니다.
  • 얼리어답터가 아닌 경우 : 자신의 친구는 무조건 얼리어답터가 되어야 합니다.
• 상태를 보면 각 노드는 하위 서브 트리의 최적해에 의존한다는 것을 알수 있습니다.
  • 따라서 DP를 이용하기로 했습니다.

결론

• 트리 순회를 하면서 각 노드의 두 가지 상태에 대해 이미 계산된 최적해(최소 얼리 어답터 수)를 저장해두고, 이를 다시 활용함으로써 중복 계산을 피해 최소 얼리어답터인의 수를 구하도록 하겠습니다.

점화식

• dp[0][v] = v가 얼리 어답터가 아닐 때의 최소 얼리 어답터 수
• dp[1][v] = v가 얼리 어답터일 때의 최소 얼리 어답터 수 (자기 자신 포함)
• 현재 노드가 얼리어답터가 아닌 경우
  • dp[0][v] += dp[1][u];
• 현재 노드가 얼리어답터인 경우
  • dp[1][v] += Math.min(dp[0][u], dp[1][u]);

 

코드

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

/**
* 백준 2533
* 사회망 서비스(SNS)
* 골드3
* https://www.acmicpc.net/problem/2533
*/
public class Boj2533 {

    private static int N; // 정점 개수
    private static List<Integer>[] tree;

    private static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        tree = new List[N + 1];
        for(int i = 1; i < N + 1; i++)
            tree[i] = new ArrayList<>();

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

            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            tree[u].add(v);
            tree[v].add(u);
        }

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

        dfs(1, new boolean[N + 1]);

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

    public static void dfs(int cur, boolean[] visited) {

        visited[cur] = true;
        dp[1][cur] = 1;
        dp[0][cur] = 0;

        for(int i : tree[cur]) {
            if(!visited[i]) {

                dfs(i, visited);

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


    }
}