[백준 / Java] 2533. 사회망서비스(SNS)

문제 정보

• 태그: DP, 트리, 트리DP
• 난이도: 골드 3

문제

입출력

풀이

트리를 DFS로 순회하면서 dp 배열에 리프노드부터 현재 노드까지의 얼리어답터의 최소 숫자를 저장하며 푸는 문제이다.

1. dp 배열 선언

static int[][] dp; 
// 행: 현재 노드가 얼리어답터인지 아닌지, 열: 현재 노드 번호, 
// 값: 현재 노드부터 시작해서 리프까지 얼리어답터 최소 수

// ...

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

주석에 적혀있다 싶이, 행은 현재 노드가 얼리어답터일때, 아닐때를 나타낸다.
0행은 현재 노드가 얼리어답터가 아님을 나타내고, 1행은 현재 노드가 얼리어답터임을 나타낸다.
열의 수는 노드의 숫자를 의미한다.

예를 들어, dp[0][3]은 리프노드부터 시작해서 3번 노드까지 왔을때, 3번 노드가 얼리어답터가 아닐 때 그 서브트리의 얼리어답터의 최소수를 의미한다.

2. dfs 함수의 구현

    static void dfs(int cur, int prev) {
        dp[0][cur] = 0; // (1)
        dp[1][cur] = 1;

        List<Integer> nexts = adj.get(cur);
        for(int next : nexts) { // (2)
            if(next == prev) continue; // (3) 트리(사이클이 없는 그래프)이므로 같은 노드를 재방문할 가능성은 부모노드 밖에 없다.

            dfs(next, cur); // (4) next를 루트로 하는 서브트리에서 얼리어답터 수를 구한다.(dp배열을 채운다)
            dp[0][cur] += dp[1][next]; // cur가 얼리어가 아니므로, next가 무조건 얼리어야만 함
            dp[1][cur] += Math.min(dp[1][next], dp[0][next]); // cur가 얼리어이므로, next는 뭐든 상관없음
        }
    }

(1) cur가 현재 서브트리의 루트가 되므로, 그 루트를 기준으로 서브트리에서 얼리어답터의 최소 수를 구할 것이다 (이것도 재귀로 더 작은 서브트리로 나눠서 구한다음 더해줄 것임). 따라서 루트가 얼리어가 아닐때는 얼리어답터의 수가 0명, 얼리어일때는 1명인 것으로 초기화 해준다.

(2) cur와 인접한 노드들을 탐색한다.

(3) 트리(사이클 없는 그래프)이므로, 인접 노드를 볼 때 같은 노드를 재방문할 가능성은 부모 노드 밖에 없다. 따라서 prev(부모)와 같이 같은지 비교하여 같으면 뛰어넘는다.

(4) next를 루트로 하는 서브트리에서 얼리어답터의 수를 구할 수 있게 dfs() 함수를 다시 호출한다. (즉, next와 그 자식 노드들의 dp 배열을 채운다.)

(5) 점화식에 의해 dp 배열을 채운다.

dp[0][cur] += dp[1][next]; // cur가 얼리어가 아니므로, next가 무조건 얼리어야만 함
dp[1][cur] += Math.min(dp[1][next], dp[0][next]); // cur가 얼리어이므로, next는 뭐든 상관없음

dfs(1, 0); // 0은 그냥 1이 루트임을 나타내는 숫자(실제 부모가 아님)
System.out.println(Math.min(dp[0][1], dp[1][1]));

dfs() 메소드가 끝나면, 1번 노드부터 리프 노드까지에서 얼리어답터의 최소 수는 dp[1][1]과 dp[0][1]에 저장되게 된다. 둘 중 더 작은 수가 답이다.

전체 코드

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

class Main {
    static int N;
    static List<List<Integer>> adj;
    static int[][] dp; // 행: 현재 노드가 얼리어답터인지 아닌지, 열: 현재 노드 번호, 값: 현재 노드부터 시작해서 리프까지 얼리어답터 최소 수
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        adj = new ArrayList<>();
        dp = new int[2][N+1];

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

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

            adj.get(a).add(b);
            adj.get(b).add(a);
        }

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

    static void dfs(int cur, int prev) {
        dp[0][cur] = 0;
        dp[1][cur] = 1;

        List<Integer> nexts = adj.get(cur);
        for(int next : nexts) {
            if(next == prev) continue;

            dfs(next, cur);
            dp[0][cur] += dp[1][next]; // cur가 얼리어가 아니므로, next가 무조건 얼리어야만 함
            dp[1][cur] += Math.min(dp[1][next], dp[0][next]); // cur가 얼리어이므로, next는 뭐든 상관없음
        }
    }
}