백준 19542 : 전단지 돌리기 (Python)

본문 링크

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

def DFS(S,pre):
    global ans
    check=0
    for i in Tree[S]:
        if i!=pre: # 이전값과 다르다면
            check=max(check,DFS(i,S))  #DFS 탐색
    if check>=D: #만약 check가 D 이상이면 ans+1 을 해준다.
        ans+=1
    return check+1 #끝에서 부터 위로 올라가는 식으로 check를 1 증가시킨다.

N,S,D=map(int,input().split())
Tree=[ [] for _ in range(N+1)]
for i in range(N-1):
    a,b=map(int,input().split())
    Tree[a].append(b)
    Tree[b].append(a)

ans=0
DFS(S,0)
print(max(0,2*(ans-1)))

📌 어떻게 접근할 것인가?

처음에 문제를 보고 이해가 되지않았습니다.
만약 $D$ 가 1일때 거리가 1 인 노드들은 전단지를 던질수 있기 때문에

2에서는 전단지를 던져서 4로 갈 필요가없고 , 5에서는 전단지를 6으로 던져서 갈 필요가 없습니다.

따라서 거리가 $D$ 이상인 노드들에 대해 거리만 찾으면됩니다.
이를 수식화 하면 최소 거리 = (단말 노드로부터 D 이상 떨어진 노드의 개수 - 1) * 2 으로 나타낼 수 있습니다.

또한 케니소프트는 항상 경로에 포함되어야 하므로, 케니소프트를 루트 노드로 시작해야합니다.

$DFS$에 이전노드와 현재노드를 넣고 , $Tree$ 를 탐색해서 이전 노드와 값이 다르다면 재귀적으로 탐색합니다.

중요한것은 재귀의 끝에 도착했을때 return check+1 을 함으로써 아래에서 위로 올라가는 식으로 길을 찾는 것입니다.

만약 아래에서 위로 올라가다가 거리가 $D$ 이상이면 $ans+=1$ 을 해줍니다.