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

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

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

---

접근

위의 그림은 문제에서 예시로 주어진 트리이다. 정점 n을 루트로 갖는 서브트리의 경우 n이 얼리어답터일 때 n의 자식 노드는 얼리어답터일 수도 있고 아닐 수도 있다. 반면 n이 얼리어답터가 아닐 때는 자식 노드들은 모두 얼리어답터이어야 한다.

 

따라서 dp라는 2차원 리스트를 생성하고 dp[n][0]일 때는 n이 얼리어답터일 때의 최소 정점 수를, dp[n][1]일 때는 n이 얼리어답터가 아닐 때의 최소 정점 수를 기록한다.

 

구현

• N-1개의 연결 정보를 바탕으로 tree에 저장하여 트리를 구성한다.
• 2차원 리스트인 dp는 dp[n][0]일 때는 정점 n이 얼리어답터일 경우, dp[n][1]일 때는 정점 n이 얼리어답터가 아닐 경우를 의미한다.
• DFS 탐색을 할 때 방문 표시를 위해 visited 리스트를 생성하였다.

N = int(input())
tree = [[] for _ in range(N + 1)]
dp = [[0, 0] for _ in range(N + 1)]
visited = [0 for _ in range(N + 1)]

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

• DFS 탐색을 진행한다.
• 현재 방문한 노드인 node가 얼리어답터일 경우를 1로 표시한다.
• 이후 현재 방문한 노드인 node의 자식 노드들을 방문하도록 한다.
• 방문한 이후에는 dp[child_node][0]에는 자식 노드가 얼리어답터일 경우 최소 정점의 수, dp[child_node][1]에는 얼리어답터가 아닐 경우 최소 정점의 수가 들어있다.
• 따라서 현재 방문한 노드가 얼리어답터일 경우 두 경우 중 최솟값을 더한다.
• 반면 현재 방문한 노드가 얼리어답터가 아닐 경우(dp[node][1])는 모든 자식 노드들이 얼리어답터이어야 하기 때문에 dp[child_node][0]을 더한다.

def dfs(node):
    visited[node] = 1
    dp[node][0] = 1
    for child_node in tree[node]:
        if not visited[child_node]:
            dfs(child_node)
            dp[node][0] += min(dp[child_node][0], dp[child_node][1])
            dp[node][1] += dp[child_node][0]

• 최종적으로 루트 노드가 얼리어답터일 경우와 그렇지 않은 경우 중 최솟값을 반환한다.

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

---

전체 코드

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

def dfs(node):
    visited[node] = 1
    dp[node][0] = 1
    for child_node in tree[node]:
        if not visited[child_node]:
            dfs(child_node)
            dp[node][0] += min(dp[child_node][0], dp[child_node][1])
            dp[node][1] += dp[child_node][0]

N = int(input())
tree = [[] for _ in range(N + 1)]
dp = [[0, 0] for _ in range(N + 1)]
visited = [0 for _ in range(N + 1)]

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

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