[Baekjoon] 2533: 사회망 서비스(SNS)

문제

문제가 조금 복잡하다.

간단히 설명하자면, 주변의 모든 친구가 얼리어답터이면 자신은 얼리어답터가 될 필요가 없는데, 이때 최소 얼리어답터의 수를 구하는 것이다.

 

풀이

대표 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Q2533 {

    private static List<List<Integer>> graph;
    private static int[][] dp;
    private static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        graph = new ArrayList<>();
        int n = Integer.parseInt(br.readLine());
        dp = new int[1000001][2];
        visited = new boolean[1000001];

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 1; i < n; i++) {
            String[] uv = br.readLine().split(" ");
            int u = Integer.parseInt(uv[0]);
            int v = Integer.parseInt(uv[1]);
            graph.get(u).add(v);
            graph.get(v).add(u);
        }

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

    public static void search(int curIndex) {
        visited[curIndex] = true;
        dp[curIndex][0] = 1;
        List<Integer> cur = graph.get(curIndex);

        for (int child : cur) {
            if (visited[child]) {
                continue;
            }

            search(child);

            dp[curIndex][1] += dp[child][0];
            dp[curIndex][0] += Math.min(dp[child][1], dp[child][0]);
        }
    }
}

계속 고민해도 답이 나오지 않아서, 다른 풀이의 힘을 빌렸다.

아이디어는 서브트리부터, 즉 리프노드부터 시작하여, 해당 노드가 얼리어답터인 경우와 얼리어답터가 아닌 경우를 나누어 주변 얼리 어답터의 최소 개수를 dp에 계속 메모이제이션 해나가는 것이다.

 

회고

역시 dp문제는 접근법을 생각해내지 못하면 풀이가 너무 어려운 것 같다.

dp문제에 익숙해지기 위해 좀 더 많은 풀이를 해봐야 될 것 같다.