ABC 333 D번 복기 - 리프 노드부터 특정 노드까지 최소로 지우는 법

1. 문제

 

D - Erase Leaves (atcoder.jp)

D - Erase Leaves

 

2. 풀이

 

리프 노드부터 차례대로 지울 수 있을때, 1번 노드를 지우기 위해서 최소로 지워야하는 노드의 개수는 몇개인가?

 

평소에 골드3정도 트리 DP 문제를 연습했더니.. 해법이 보이긴 하더라

 

리프 노드라는 것은 자식이 없는 노드인데, 목표로 하는 노드가 1번 노드니까,

 

1번 노드를 루트라고 생각한다면.. 다음과 같은 트리는

 

 

 

 

다음과 같이 바꿀 수 있는데, 이런 경우에 리프 노드부터 지워나간다고 생각한다면 해법이 보인다

 

 

즉, 1번 노드의 두 자식 2번 노드와 6번 노드 각각을 루트로 하는 서브트리가 가지고 있는 노드의 개수만큼 지워나갈때,

 

마지막으로 1번 노드를 지울 수 있게 된다.

 

 

 

따라서 트리 DP로 정점 u를 루트로 하는 서브트리가 포함하는 정점의 개수를 모두 구하고

 

1번 노드의 자식 v1,v2,...,vn에 대하여 1번을 지울때까지 v1,v2,v3,..,vn이 포함하는 서브트리를 지우면 되는데

 

다음과 같은 트리를 보면..

 

 

 

이 경우는 어떻게 생각해야할까?

 

1번을 루트로 생각한다면, 5번,6번 리프 노드부터 지워나가야하지만..

 

애초에 문제에서 1번이 루트라고 한적이 없고 내가 임의로 정한 루트이기 때문에,

 

사실 다른 정점이 루트라고 한다면 1번은 리프노드가 될 수 있다

 

따라서 이런 경우는 바로 1번을 지우면 된다.

 

 

 

그러므로 모든 정점 u를 루트로 하는 서브트리의 노드 개수를 모두 구하고, 

 

1번의 자식 노드 v1,v2,..,vn에 대하여 하나의 자식을 제외한 나머지 노드 v1,v2,..,vn-1의 개수만큼 모두 지우고,

 

나머지 1번을 지우면 된다.

 

하나의 자식은 뭘 남겨야 최소 개수만큼 지우는가?

 

v1,v2,..,vn 중 n-1개를 선택해서 지운 개수가 최소가 되도록 선택?

 

n이 매우 크면 시간이 너무 오래걸릴 수 있다.

 

하지만 v1,v2,..,vn중 최댓값 max_v를 제외한 나머지를 모두 지우면 된다.

 

만약 v1,v2,..,vn중 max_v를 지우게 된다면 지우는 노드 개수는 무조건 최소 개수를 넘어가기 때문에 모순이 된다.

 

from sys import stdin,setrecursionlimit
setrecursionlimit(500000)

#리프노드부터 시작해서 1번 노드를 지우기까지 최소 개수를 지우는 방법

#먼저 u를 루트로 하는 서브트리의 노드 개수를 모두 구한다
def dfs(u):
    
    dp[u] = 1
    
    for v in tree[u]:
        
        if visited[v] == 0:
            
            visited[v] = 1
            dfs(v)
            dp[u] += dp[v]

n = int(stdin.readline())

tree = [[] for _ in range(n+1)]

for _ in range(n-1):
    
    u,v = map(int,stdin.readline().split())
    tree[u].append(v)
    tree[v].append(u)

visited = [0]*(n+1)
visited[1] = 1

dp = [0]*(n+1)

dfs(1)

answer = 0

ind = -1
cost = 0

for v in tree[1]:
    
    if dp[v] > cost:
        
        cost = dp[v]
        ind = v

#1번에 연결된 자식 정점이 v1,v2,..,vn이라고 한다면...
#v1,v2,...,vn을 루트로 하는 서브트리의 노드 개수의 최댓값 max_v를 제외한
#나머지 노드들을 모두 지우고, 1번을 지우면 최소 개수만큼 지우게 된다.
#왜냐하면 max_v를 지운다면 어떻게 지우더라도 무조건 최소 개수를 넘어가게 된다.
for v in tree[1]:
    
    if v != ind:
        
        answer += dp[v]

print(answer+1)

  

 

 

리프노드는 트리를 어떻게 만드느냐에 따라 다르다.

 

tree[a].append(b), tree[b].append(a)로 양방향으로 구현하면... 리프노드는 tree[u]의 원소 개수가 1개일때고

 

부모 > 자식 연결 tree[a].append(b)로 단방향으로 구현한다면 리프노드는 tree[u]의 원소 개수가 0개일때고..

 

 

또한 재귀 DFS라서 recursionlimit를 늘려줘야하고..

 

빠른 입출력 써야되는데.. 귀찮아서 안썼더니 RE, TLE가 나더라고

 

쓸데없는짓 안했으면 AC받은거나 마찬가지라..?