트리 탐색 테크닉2 - 현재 노드에서 가장 먼 자식 노드까지의 거리

1. 문제

 

19542번: 전단지 돌리기 (acmicpc.net)

19542번: 전단지 돌리기

 

2. 풀이

 

트리로 구성된 그래프에서 모든 노드에 전단지를 돌려야하는데, 현재 노드에서 거리가 D이하인 모든 노드에 전단지를 한번에 돌릴 수 있다고 한다

 

트리 구조이기 때문에 부모 > 자식으로 내려가면서 각 노드마다 가장 먼 자식 노드까지의 거리를 안다면,

 

어디 노드까지만 방문해도 되는지를 파악할 수 있을 것이다.

 

10만개의 노드가 있어서 한번의 DFS로 각 노드마다 가장 먼 자식 노드까지의 거리를 구해야하는데

 

이게 참 쉽지 않다

 

리프 노드까지 일단 내려간 다음에, 리프 노드에서의 값을 0으로 두고, return하면서 +1씩 올려주는 것이다.

 

 

루트인 1번에서 시작해서 쭉 내려간 다음, 6번에 도달하면 이 때 값을 0으로 두고,

 

0에 1을 더한 값을 return해주는 것이다.

 

그러면 5에 1이 오고, return되면서 4에 2가 되고, return되면서 2에서 3이 오고, return되면서 1에 4가 오고

 

 

 

그러면 1번 노드는 가장 먼 자식 노드까지의 거리가 4, 2번 노드는 3, 4번 노드는 2, 5번 노드는 1, 6번 노드는 0이다.

 

그런데 트리는 여러 방향으로 내려갈 수 있는데, 다음과 같은 경우...

 

1번 노드에서 9번 노드까지 내려갔을때, 최대 거리가 5이다.

 

그래서 항상 거리의 최댓값으로 갱신해줘야한다.

 

 

#현재 노드 u에서 가장 먼 자식 노드까지의 거리
#리프 노드까지 쭉 내려간 다음, 그 때 값을 0으로 두고,
#1씩 올리면서 return
#여러 방향으로 내려갈 수 있으므로, 얻은 값의 최댓값으로 갱신해나가기
def dfs(u):
    
    dist = 0

    for v in tree[u]:

        if visited[v] == 0:

            visited[v] = 1
            
            d = dfs(v)

            if dist < d:
                
                dist = d
                
    child[u] = dist

    return dist+1

 

 

이렇게 해서 루트부터 탐색을 한다면 모든 노드에서 가장 먼 자식 노드까지의 거리를 찾을 수 있다.

 

그러면 루트부터 탐색을 한다고 할때, 어떤 노드 u에 도달했다고 하자.

 

u에서 가장 먼 자식 노드까지의 거리가 D이상이라면? 어쨌든 u번 노드는 방문해줘야한다.

 

D보다 작다면? 이전에 방문된 노드에서 전단지를 이미 뿌려줬다

 

1번에서 시작한다고 해보고, D = 3이라면... 현재 가장 먼 자식 노드까지 거리는 5이므로 해당 노드는 방문해야한다

 

 

그래서 2번 노드로 왔는데, 2번 노드에서는 가장 먼 자식 노드까지 거리가 4이므로, 아직 9번 노드까지 전단지를 던지지 못한다

 

 

 

그러다가 4번 노드로 가보면, 가장 먼 자식 노드까지 거리는 2이므로 이미 2번 노드에서 4번 노드에 전단지를 던져줬다고 생각할 수 있다.

 

그래서 4번 노드는 방문할 필요가 없다

 

 

 

그러다가 3번 노드로 왔는데, 가장 먼 자식 노드까지 거리가 3이므로, 나머지 7,8,9번 노드에 전단지를 던져줄 수 있어서

 

방문해야한다.

 

방문하지 않으면 2번 노드에서 9번 노드에 전단지를 던지지 못한다

 

 

 

그래서 가장 먼 자식 노드까지 거리가 D 이상인 1,2,3번 노드까지만 방문해보면 모든 노드에 전단지를 던질 수 있게 된다.

 

따라서, 가장 먼 자식 노드까지 거리 배열을 구한 다음, 해당 배열을 순회해서 거리가 D 이상인 노드 수를 센다면...

 

그 노드가 M개 일때, 간선의 수는 M-1개이므로, 왕복하면 2*(M-1)이 최소 이동 거리가 된다.

 

그런데 M = 0일 수 있는데, D가 너무 큰데 가장 먼 자식 노드 까지 거리가 작은 경우, 아무 노드도 방문 안해도 되는데

 

예시) 

3 1 3

1 2

2 3

 

그러면 이동 거리는 0이어야 하나, 2*(M-1)은 음수가 나오니 이런 경우는 예외처리해줘서

 

n,s,d = map(int,stdin.readline().split())

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

for _ in range(n-1):

    a,b = map(int,stdin.readline().split())

    tree[a].append(b)
    tree[b].append(a)

visited = [0]*(n+1)
child = [0]*(n+1)
visited[s] = 1
dfs(s) #각 노드에서 가장 먼 자식 노드까지 거리를 모두 구한다

count = 0

#가장 먼 자식 노드까지 거리가 d이상인 노드만 방문하면 된다
for i in range(1,n+1):
    
    if child[i] >= d:
        
        count += 1

#d가 매우 커서, 아무 노드도 방문하지 않은 경우 2*count-2 < 0인데, 
#아무 노드도 방문하지 않으면 이동 거리는 0이어야하니..
print(max(2*count-2,0))