[python] 백준 2533 사회망 서비스(SNS)

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

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

 

문제 해결

• 트리를 이용해야하는데 어떻게 이용해야할지 고민을 많이 했다.
• 부모-자식 중에서 적어도 한 명은 얼리 어답터여야한다.
• 따라서 dp를 이용해서 부모가 얼리 어답터일 때(dp[parent][1])일 때와 부모가 얼리 어답터가 아닐 때 (dp[parent][0])를 구분을 해서 알고리즘을 풀어나가면 되겠다라는 생각을 한다.
  • dp[i][j]는 i번째 노드가 j상태일때 i번째 밑에 있는 노드들중에 얼리 어답터인 노드의 개수를 의미한다.
• 부모가 얼리 어답터이면 자식은 얼리어답터여도 되고 아니여도 된다. 따라서 dp[parent][1] += min(dp[child])
• 부모가 얼리 어답터가 아니면 자식은 얼리어답터여야하므로 dp[parent][0] += dp[child][1]

CODE

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

def dfs(node):
    for next in graph[node]:
        if not visited[next]:
            visited[next] = True
            dfs(next)
            dp[node][0] += dp[next][1] # node가 얼리어답터가 아니면 node의 자식들은 모두 얼리 어답터야하기 때문
            dp[node][1] += min(dp[next]) # node가 얼리어답터이면 node의 자식들은 얼리 어답터이든 아니든 상관 없음. 최소 얼리 어답터의 수를 구하면 됨.
if __name__=='__main__':
    n = int(input())
    graph = [[] for _ in range(n+1)]
    for _ in range(n-1):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)
    dp = [[0,1] for _ in range(n+1)]
    visited = [False for _ in range(n+1)]
    visited[1] = True
    dfs(1)
    print(min(dp[1]))