백준 - [Gold 2] 2533번 사회망 서비스(SNS)

문제링크: https://www.acmicpc.net/problem/2533

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

---

문제 설명

- N: 정점의 개수

- 친구 관계 (u, v) N-1개 주어짐

 

위와 같은 입력이 주어졌을 때, 모든 노드와 관계를 맺고있는 최소의 노드 개수를 구하는 문제입니다.

여기서는 얼리어답터라고 칭합니다. 얼리어답터 = 관계를 맺는 주체

위와 같은 그림이 주어지면 2, 3, 4가 얼리어답터이고 나머지는 얼리어답터가 아닙니다. 최소의 개수는 3입니다.

1, 5, 6, 7, 8도 가능하지만 최소의 개수가 아니여서 정답이 아닙니다.

---

풀이

트리에다가 DP를 활용한 문제입니다. (저도 아직 정확히 이해하지 못했습니다.... ㅠ)

DP에 대해 정의를 시작해 보겠습니다.

 

DP(i) = i 를 root로 하는 subtree 의 최소 얼리 어답터 수

 

하지만 i가 얼리어답터인지 아닌지에 따라 2가지 경우로 나뉨

1. 현재 노드가 얼리어답터 -> 인접한 다음 노드 얼리어답터 x

2. 현재 노드가 얼리어답터 x -> 인접한 다음 노드는 얼리어답터 or x

 

j 추가 -> i가 얼리어답터인지 아닌지의 여부

 

최종 점화식

- DP( i, true) = min(DP(i 의 자식, true), DP(i 의 자식, false))들의 총합 + 1

i 가 얼리어답터면은 자식 노드가 얼리어답터인 경우와 아닌 경우 두 부분을 구해야 함

여기에 root가 얼리 어답터니까 + 1

 

- DP( i, false) = DP(i 의 자식, true) 들의 총합 

i 가 얼리어답터가 아닌 경우는 자식 노드는 무조건 얼리어답터 여야함

 

위와 같이 두가지 경우에 대해서 정답을 구해주어야 하는 문제입니다.

DFS로 각 노드의 하위트리들을 구해주고, 각 노드의 하위트르들을 가지고 DP를 돌려주면 되는 문제입니다.

 

코드

import sys
from sys import stdin

sys.setrecursionlimit(10**9)

def DFS(cur):
    visited[cur] = True
    for i in edges[cur]:
        if not visited[i]:
            child[cur].append(i)
            DFS(i)

def get_dp(cur, check):
    if check: # 얼리어답터면
        # DP( i, true) = min(DP(i 의 자식, true), DP(i 의 자식, false))들의 총합 + 1
        if dp[cur][1] != -1:
            return dp[cur][1]
        dp[cur][1] = 1 # 본인이 얼리어답터니 + 1을 해주는 것이다.
        for i in child[cur]: # 하위 노드 탐색
            dp[cur][1] += min(get_dp(i, False), get_dp(i, True))
        return dp[cur][1]
    else: # 얼리어답터가 아니며
        # DP( i, false) = DP(i 의 자식, true) 들의 총합 
        if dp[cur][0] != -1:
            return dp[cur][0]
        dp[cur][0] = 0 # 얼리어답터가 아니므로 0
        for i in child[cur]: # 하위 노드 탐색
            dp[cur][0] += get_dp(i, True) #
        return dp[cur][0]


stdin = open("input.txt", "r")

# N 노드의 개수
N = int(stdin.readline()) 

edges = [[] for _ in range(N+1)]
child = [[] for _ in range(N+1)]

# (u, v) N-1개
for _ in range(N-1):
    u, v = map(int, stdin.readline().rstrip().split())
    # 양방향 추가
    edges[u].append(v)
    edges[v].append(u)

dp = [[-1, -1] for _ in range(N+1)] # dp 초기화
visited = [False] * (N+1)

DFS(1)
print(min(get_dp(1, False), get_dp(1, True)))

DP를 어려워해서 정답을 보고 풀고 이해하는데도 시간이 많이 걸렸습니다.

 

풀이는 https://www.weeklyps.com/entry/BOJ-2533-사회망-서비스를 참조해서 하였습니다. 감사합니다.