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

문제

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

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

해설

트리에서의 DP를 이용해서 해결할 수 있는 문제입니다.

 

일반적으로 일차원 배열이나, 이차원 배열에 관한 DP를 풀 때는 반복문을 순회하면서 이전값을 현재값을 구하는 데 활용하는데요. 트리는 이러한 구조가 현재 노드와 자식 노드가 갖는 서브트리로 치환되어 나타난다는 점에서만 그 형태가 다르다고 볼 수 있습니다.

 

따라서, 기본적으로 트리를 활용한 DP를 적용하기 위해서는 DFS 탐색을 통해 가장 깊은 곳에 있는 단말 노드(Leaf Node)부터 처리해주는 것을 생각해야 합니다.

 

 

문제로 돌아와서 생각해보겠습니다.

 

이 문제에서 트리의 모든 노드가 얼리어답터가 되기 위해서는 각 노드의 친구가 얼리어답터이거나, 자신이 얼리어답터이면 됩니다. 따라서 DP를 생각할 때 고려해야 하는 변수, 즉, 변하는 상황은 '얼리어답터인가?'의 여부로 생각할 수 있게 되죠.

 

그렇다면 이제 얼리어답터의 여부와 그 이전의 상황(서브트리)이 현재에 어떻게 영향을 미치는지를 고민해봐야 합니다. 그러면 앞서 말한것처럼 '현재 노드가 얼리어답터일 때', '얼리어답터가 아닐 때'로 나누어 아래와 같이 두 가지 상황을 생각해볼 수 있습니다.

 

1. 현재 노드가 얼리어답터일 때: 주변의 모든 노드가 얼리어답터여야 한다.

2. 현재 노드가 얼리어답터가 아닐 때: 주변의 노드에 영향을 받지 않는다.

 

그리고 트리 DP에서는 단말 노드가 처음으로 초기화되기 때문에 자기 자신에 대해서 만약 자신이 얼리어답터라면 자신의 DP값을 1로 초기화하고, 자신이 얼리어답터가 아니라면 DP값을 0으로 초기화해주면 됩니다. 

 

마지막으로 트리의 아래부터 위로 순회하면서 자신의 처지(얼리어답터인가의 여부)에 따라 주변 친구들의 DP값을 나의 상황에 더해주면 됩니다. 그러면 결국 맨 마지막에 루트 노드에서 정답이 만들어지게 됩니다.

 

풀이는 아래와 같습니다.

 

풀이 - 파이썬

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(node):
    visited[node] = True
    dp[node][0], dp[node][1] = 0, 1

    for child in tree[node]:
        if not visited[child]:
            dfs(child) # 자식노드부터 처리한다.
            dp[node][0] += dp[child][1] # 내가 얼리어답터가 아닐 때
            dp[node][1] += min(dp[child][0], dp[child][1]) # 내가 얼리어답터일 때

n = int(input())
tree = defaultdict(list)
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

# dp[i][0] = 내가 얼리어답터가 아닐 때 필요한 친구의 수
# dp[i][1] = 내가 얼리어답터일 때 필요한 친구의 수
dp = [[0] * 2 for _ in range(n+1)]
visited = [False] * (n+1)
dfs(1)
print(min(dp[1][0], dp[1][1]))

풀이 - 자바

package PS;

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

public class B_2533 {
    static int n;
    static boolean[] visited;
    static int[][] dp;
    static ArrayList<Integer>[] tree;

    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());
        visited = new boolean[n+1];
        dp = new int[n+1][2];
        tree = new ArrayList[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 a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            tree[a].add(b);
            tree[b].add(a);
        }
        dfs(1);
        System.out.println(Math.min(dp[1][0], dp[1][1]));
    }

    // dp[i][0] = 내가 얼리어답터가 아닐 때 필요한 친구의 수
    // dp[i][1] = 내가 얼리어답터일 때 필요한 친구의 수
    public static void dfs(int node){
        visited[node] = true;
        dp[node][1] = 1; dp[node][0] = 0;
        for(Integer child : tree[node]){
            if(!visited[child]){
                dfs(child); // 자식노드부터 처리한다.
                dp[node][0] += dp[child][1]; // 내가 얼리어답터가 아닐 때
                dp[node][1] += Math.min(dp[child][0], dp[child][1]); // 내가 얼리어답터일 때
            }
        }
    }
}