[BOJ] Q2533 사회망 서비스(SNS)

[BOJ] Q2533 사회망 서비스(SNS)

Question

Language: Python

Difficulty: Gold 3

Tree 와 DP를 결합한 응용 문제이다.

자식 노드를 처리하면서 루트 노드까지의 dfs를 통해 처리를 이어나간다.

부모 노드와 자식 노드 관계에서

부모노드는 얼리어댑터가 되는 경우, 얼리어댑터가 되지 않는 경우로 나눠서 생각할 수 있다.

얼리어댑터가 되는 경우에는 자식 노드에 대해서 얼리어댑터가 없어도 상관이 없다. 따라서, 각각의 자식 노드에 대해서, 얼리어댑터인 경우와 얼리어댑터가 아닌 경우 중 작은 값을 선택해서 모든 자식 노드의 값들을 합한다.

dfs를 진행함에 있어, 얼리어댑터가 되는 경우와 얼리어댑터가 되지 않는 경우를 비교해서 작은 값을 반환한다.

dp[vertex][1]+=solution(child)

부모노드가 얼리어댑터가 되지 않는 경우에는, 모든 자식 노드가 얼리어댑터인 경우이다.

dp[vertex][0]+=dp[child][1]

주의점

visited 배열을 이용해서 노드 간의 재방문을 허용하지 않도록 하고, 트리와 같이 처리 될 수 있도록 한다.

Solution

import sys
def solution(vertex):
    global dp,visited

    visited[vertex]=True

    for child in graph[vertex]:
        #재방문을 하지 않도록 한다. --> 트리
        if visited[child]:
            continue
        #얼리어댑터가 되는 경우: 자식노드의 값중 작은 값을 취해서 더한다.
        dp[vertex][1]+=solution(child)
        #얼리어댑터가 되지 않는 경우, 자식노드가 얼리어댑터 인경우의 값들을 더한다.
        dp[vertex][0]+=dp[child][1]
    #dp[vertex][0]: 해당 노드가 얼리어댑터가 아닌 경우
    #dp[vertex][1]: 해당 노드가 얼리어댑터가 되는 경우
    #이 두 가지 중 작은 값을 반환한다. --> 이러한 작업은 모든 자식 노드에 대해서 실행한다.
    return min(dp[vertex])
    
if __name__ == "__main__":
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline 
    N=int(input())
    graph=[[] for _ in range(N+1)]
    visited=[False] * (N+1)
    for _ in range(N-1):
        v1,v2=map(int,input().split())
        graph[v1].append(v2)
        graph[v2].append(v1)
    
    dp=[[0,1] for _ in range(N+1)]
    
    print(solution(1))