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

📝 BaekJoon 2533번 : 사회망 서비스(SNS) (G3 37.490%)

---

🔎 사회망 서비스(SNS) 문제

---

📌 아이디어

트리를 이용한 DP 기본 문제이다.

---

💭 풀이

• 이전에 풀었던 문제와 비슷하게 독립집합인 문제로 생각할 수도 있는데 문제의 조건에서 자신의 친구들이 모두 얼리 어답터일 경우 자신도 의견을 받아들인다고 한다.
• 이 조건에 따라 만약 DP[node][0]는 node가 얼리어답터가 아닌 경우, DP[node][1]는 node가 얼리어답터일 경우라고 할 때 DP[node][0]에서 올 수 있는 값은 node에 연결된 노드들이 모두 얼리어답터일 경우가 되게 된다. 만약 DP[node][1]일 경우에는 나랑 연결된 노드들이 얼리어답터일 수도, 아닐 수도 있다.
• 해당 조건에 따라 본다면 node에 연결된 노드들을 i라고 가정했을 때 DP[node][0]는 node에 연결된 모든 i에 대하여 + DP[i][1]이어야 하고 DP[node][1]은 node에 연결된 모든 i에 대하여 min(DP[i][0], DP[i][1])값을 가지며 최솟값을 가지게 된다.
• 이 과정을 임의의 한 node로부터 시작해서 dfs를 통해 바텀 업 방식으로 값이 업데이트가 되게 된다. dfs를 이용할 경우 재귀에서의 Runtime Error나 메모리 초과가 될 수 있으니 주의 해야 한다.

---

💻 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
      
def dfs(start) :
    dp[start][1] = 1
    check[start] = True

    for i in tree[start] :
        if not check[i] :
            dfs(i)
            dp[start][0] += dp[i][1]
            dp[start][1] += min(dp[i][0],dp[i][1])

n = int(input())

tree = [[] for _ in range(n+1)]
dp = [[0,0] for _ in range(n+1)]
check = [False] * (n+1)

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

dfs(1)

print(min(dp[1][0], dp[1][1]))

---