문제 링크
https://www.acmicpc.net/problem/2533
🕒 Python 풀이시간: 60분
import sys
sys.setrecursionlimit(1000001)
input=sys.stdin.readline
n=int(input())
graph=[[] for _ in range(n+1)]
for _ in range(n-1):
u,v=map(int,input().split())
graph[u].append(v)
graph[v].append(u)
dp=[-1]*(n+1)
def dfs(v):
noChild=True
for i in graph[v]:
if not visited[i]:
noChild=False
break
if noChild:
dp[v]=0
return 0
if dp[v]!=-1:
return dp[v]
dp[v]=0
for i in graph[v]:
if not visited[i]:
visited[i]=True
k=dfs(i)
if k==0:
dp[v]=1
return dp[v]
visited=[False]*(n+1)
visited[1]=True
dfs(1)
print(sum(dp[1:]))얼리어답터 최소 수: SNS 트리 문제 해결하기! 📱🌳
사회망 서비스(SNS)를 연결해서 얼리어답터의 최소 수를 갱신해 나가는 DP이자 트리문제이다. 문제에서 주어진 조건 자체가 트리를 띄고있기 때문에 트리문제라고 까지는 간단히 접근할 수 있다.
이제 얼리어답터의 최소 수를 갱신하는데 필요한 조건을 따져봐야 한다. 각 끝에 있는 노드, 즉 리프노드에 한해서는 얼리어답터가 될 필요가 없고 0으로 갱신하면 된다. 만약 자식 중 하나라도 0이라면 즉, 자식 노드 중 하나가 얼리어답터가 아니라면 현재 노드는 얼리어답터가 되어야 하므로 1로 갱신하면 된다. 이런 식으로 전의 해가 현재 해에 영향을 주는 식의 문제이므로 DP를 통해 단순화하여 풀 수 있다. 여기서는 다른 해를 누적 시킬 필요 없이 자식 중 0이 있는지, 또 현재 노드가 리프 노드인지만 확인 하면 된다. 그렇게 된다면 DP에 얼리어답터와 얼리어답터가 아닌 사람들로 갱신이 될테고, DP에 있는 모든 1의 갯수를 구해주면 최소 얼리어답터의 수가 된다.
이렇게 Python으로 백준의 "사회망 서비스(SNS)" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
