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

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

 

---

🧠 알고리즘

• 트리 DP

 

✔️ 동작 방식

• 그래프(트리) 구조를 인접 리스트(conn_dict)로 구성한다.
• 각 노드에 대해 두 가지 상태를 정의한다:
  • dp[node][0]: 해당 노드가 얼리어답터가 아닐 때 필요한 최소 얼리어답터 수
  • dp[node][1]: 해당 노드가 얼리어답터일 때 필요한 최소 얼리어답터 수
• DFS로 트리를 순회하면서, 자식 노드들의 DP 값을 이용해 현재 노드의 DP 값을 계산한다.
  • 현재 노드가 얼리어답터가 아니면, 모든 자식은 반드시 얼리어답터여야 하므로
    dp[node][0] += dp[child][1]
  • 현재 노드가 얼리어답터라면, 자식은 얼리어답터이든 아니든 상관없으므로
    dp[node][1] += min(dp[child][0], dp[child][1])
• 루트 노드(1번 노드)에서 min(dp[1][0], dp[1][1]) 값을 결과로 출력한다.

---

 

 

🧾 코드

import sys

def _dfs(num):
    global conn_dict
    global dp
    global visit

    visit[num - 1] = True

    for next_num in conn_dict[num]:
        if not visit[next_num - 1]:
            _dfs(next_num)
            dp[num][0] += dp[next_num][1]
            dp[num][1] += min(dp[next_num][0], dp[next_num][1])
    

def _main(n):
    global conn_dict
    global dp
    global visit
    conn_dict = {i: []  for i in range(1, n + 1)}
    """
        dp
        인덱스 0 >> 얼리어답터 놉놉
        인덱스 1 >> 얼리어답터!!
    """
    dp = {i: [0, 1] for i in range(1, n + 1)}
    visit = [False] * n

    for _ in range(n - 1):
        a, b = map(int, sys.stdin.readline().rstrip().split())
        conn_dict[a].append(b)
        conn_dict[b].append(a)

    _dfs(1)
    return min(dp[1])


n = int(sys.stdin.readline().rstrip())
print(_main(n))

---

 

⏱️ 시간 복잡도

_dfs() : 모든 간선 한번씩 방문 ( 선형 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )