알고리즘 - Python / 백준 - 2533번 : 사회망 서비스(SNS)

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

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

 

---

알고리즘 설명

• 트리 구조와 DP를 합친 Tree DP 문제다.
• DP의 경우 부문제의 최적해가 모여 전체 문제의 최적해가 찾을 수 있는 경우에 사용할 수 있다.
• 트리 구조의 경우 서브 트리들이 모여 전체 트리를 이루기 때문에 서브 트리의 최적해들을 통해 전체 트리의 최적해를 찾을 수 있다면 트리 구조에도 DP를 사용할 수 있다.
• 서브 트리들의 경우 구분할 수 있는 가장 좋은 포인트는 해당 서브트리의 ROOT 노드다.
• 따라서 구분되는 서브트리들의 ROOT 노드를 통해 DP 배열을 구성할 수 있다.
• 예를 들어 DP[ROOT노드 번호][A][B] ... 이런 식으로 문제 타입에 맞게 A,B... 를 세팅할 수 있다.
• 대부분의 Tree DP는 DFS를 통해 리프 노드까지 나아가고 리프 노드 부터 부문제를 해결하면서 위쪽으로 차근차근 올라온다.
• 즉 리프 노드쪽 부터 부문제를 해결해보면 마지막에는 최종 본 트리의 ROOT 노드의 본 문제를 해결할 것이고 앞에서 구한 것들을 통해 최적해를 구할 수 있을 것이다.

 

 

풀이

• 이 문제의 경우 트리에서 현재 노드가 취할 수 있는 행동은 얼리어답터가 되거나 되지 않거나 이다.
• 각 경우에 대해 최적해가 어떻게 나올지 생각해보자.
• 서브 트리의 최적해를 구하는 것이므로 , 내 자식 노드들은 이미 최적해를 구해 왔다고 생각해야 한다.
• 얼리어답터가 아닌 경우 : 내가 얼리어답터가 아니므로 , 내 자식들은 모두 얼리어답터여야 한다.
• 따라서 DP[현재 노드] = DP[내 자식 노드들][얼리어 답터인 경우의 최적해] 가 될 것이다.
• 얼리어답터인 경우 : 내가 얼리어답터 이므로 , 내 자식들을 얼리어답터여도 되고 , 그렇지 않아도 된다.
• 따라서 DP[현재 노드] = MIN( DP[내 자식 노드들][ 얼리어답터인 경우 최적해] , DP[내 자식 노드들][ 얼리어답터가 아닌 경우 최적해 ) 가 될 것이다.
• 위의 경우 코드로 구현하기 위해 DP 배열을 DP[현재 노드][얼리어 답터 여부] 으로 두었고 얼리어답터 여부가 1인 경우는 얼리어답터인 경우 , 0인 경우는 얼리어답터가 아닌 경우로 두었다.
• 전체 트리를 DFS를 통해 순회하면서 아래서부터 부분해를 구하여 마지막 본문제의 최적해를 구하면 된다.

 

 

리뷰

• 코드를 완성하고 제출하니 재귀오류 [런타임 에러 (RecursionError)]가 났다.
• 재귀 깊이를 늘려주어 pypy로 제출하니 메모리 초과가 났다.
• 내 기억상으로는 pypy는 python3 보다 속도가 빠른 반면 메모리 효율이 조금 떨어지는 것으로 알고 있다.
• 메모리 초과를 막기 위해 같은 코드를 다시 python3로 제출하니 정답이 나왔다.

 

 

import sys
sys.setrecursionlimit(10 ** 9)
n = int(sys.stdin.readline())
c = [[] for i in range(n+1)]
dp = [[0,0] for i in range(n+1)]

for _ in range(n-1):
    a,b = map(int , sys.stdin.readline().split(" "))
    c[a].append(b)
    c[b].append(a)

visited = [0 for i in range(n+1)]
def dfs(start):
    global c
    global visited
    visited[start] = 1
    if len(c[start]) == 0:
        dp[start][1] = 1
        dp[start][0] = 0
    else:
        for i in c[start]:
            if visited[i] == 0:
                dfs(i)
                dp[start][1] += min(dp[i][0] , dp[i][1])
                dp[start][0] += dp[i][1]
        dp[start][1] += 1

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

---