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

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

 

인생 첫 트리에서의 다이나믹 프로그래밍... 이어서 고민을 제법 많이 했다.

 

먼저 트리에서 다이나믹 프로그래밍을 어떻게 하지? 했는데 DFS를 활용하는 듯했다.

https://orijeje.tistory.com/40

[알고리즘] 트리에서의 다이나믹 프로그래밍(Tree DP)

위 블로그에서 DFS를 기반으로한 DP 코드를 간단하게 적어두어 이를 참고했다.

void dfs(int cur){
    if(visited[cur])
        return;
    visited[cur] = 1;
    for(auto next : tree[cur]){
        if(visited[next])
            continue;
        dfs(next);
        //dp 테이블을 채우는 어떠한 코드
        dp[cur] = fill_dp_table(next);
    }
}

 

이후 내가 생각한 얼리어답터의 조건은 다음과 같았다.

1. node의 자식이 하나라도 leaf이면 node는 얼리어답터이다.

2. 현재, node가 얼리어답터가 아닌데, 자식도 얼리어답터가 아니라면, node는 얼리어답터이다.

 

다음의 조건으로 코드를 짜보았다.

# https://www.acmicpc.net/problem/2533
# DP, Tree

from collections import defaultdict
import sys

sys.setrecursionlimit(1000000000)

N = int(input())

graph = defaultdict(list)
for n in range(N-1) :
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

visited = [0] * (N+1)
early_adaptor = [0] * (N+1)
is_leaf = [0] * (N+1)

def DFS(node) :
    global graph
    global is_leaf
    global visited
    global early_adaptor

    if visited[node] != 0 :
        return
    
    visited[node] = 1
    if len(graph[node]) == 1 and visited[node] == 1 :
        is_leaf[node] = 1
    for e in graph[node] :
        if visited[e] :
            continue

        DFS(e)

        if is_leaf[e] == 1 :
            early_adaptor[node] = 1
        elif early_adaptor[node] == 0 and early_adaptor[e] == 0 :
                early_adaptor[node] = 1

DFS(1)
print(sum(early_adaptor))

얼리어답터일 때, early_adaptor 배열에 해당하는 node번째에 1을 할당하고 

나중에 정답은 sum(early_adaptor)로 하여 전체 최소 얼리어답터 수를 구했다.