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

접근

바로 전에 풀었던 트리의 독립집합에서 썼던 방법과 비슷하게 DFS 알고리즘을 사용하여 문제를 풀 수 있다.

유사 문제: 2021.05.05 - [코딩/백준 (Python)] - 백준 2213번: 트리의 독립집합 (Python)

백준 2213번: 트리의 독립집합 (Python)

유사하게 dp를 사용하면서 dp[i][0] 에는 i 노드가 얼리어답터일 때의 서브 트리에서 얼리어답터의 최소값, dp[i][1] 에는 i 노드가 얼리어답터가 아닐 때의 서브트리에서 얼리어답터의 최소값을 갱신해주면 된다. a를 부모노드로 갖는 b, c 자식 노드가 있을 때, a 가 얼리어답터일 경우 자식 노드 b 나 c 는 얼리어답터여도 되고 아니어도 된다. 하지만 자식노드 중 하나라도 얼리어답터가 아닐 경우 a 는 무조건 얼리어답터이어야 한다는 점을 생각하고 문제를 풀면 해결할 수 있다.

코드

import sys

sys.setrecursionlimit(10 ** 9)
n = int(sys.stdin.readline())
lines = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, sys.stdin.readline().split())
    lines[a].append(b)
    lines[b].append(a)
dp = [[0, 0] for _ in range(n + 1)]
visited = [0 for _ in range(n + 1)]


def dfs(r):
    visited[r] = 1
    dp[r][0] = 1
    for i in lines[r]:
        if not visited[i]:
            dfs(i)
            dp[r][0] += min(dp[i][0], dp[i][1])
            dp[r][1] += dp[i][0]


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

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!