[백준] 20924번 - 트리의 기둥과 가지 Python, Java

문제

시청 공무원 마이크로는 과장으로부터 시에 있는 나무의 기둥의 길이와 가장 긴 가지의 길이를 파악하라는 업무 지시를 받았다.

마이크로는 ICPC Sinchon Winter Algorithm Camp에서 배운 트리 자료 구조를 이용하면 이 작업을 좀 더 수월하게 할 수 있으리라 판단했다.

기가 노드는 루트 노드에서 순회를 시작했을 때, 처음으로 자식 노드가 $2$개 이상인 노드다. 기둥-가지를 줄여 기가 노드라 이름 붙였다. 위 그림에서 기가 노드는 $4$번 노드다.

단, 위 그림과 같이 리프 노드가 단 $1$개인 경우 리프 노드가 동시에 기가 노드가 된다.

또한, 위 그림과 같이 루트 노드가 동시에 기가 노드인 경우도 가능하다.

• 트리의 기둥은 루트 노드에서부터 기가 노드까지다. 위 그림에서 기둥은 $1-2-3-4$

• 트리의 가지는 기가 노드에서부터 임의의 리프 노드까지다. 위 그림에서 가지는 $4-5-6-7$

마이크로는 시의 나무를 트리 자료 구조로 옮겼다. 그런데 과장이 마이크로에게 또 다른 업무를 지시했다! 너무 바쁜 마이크로를 대신해 트리의 기둥과 가장 긴 가지의 길이를 측정하자.

입력

첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$

이후 $N-1$

트리가 아닌 그래프는 입력으로 주어지지 않는다.

출력

나무의 기둥의 길이와 가장 긴 가지의 길이를 출력한다.

예제 입력 1

12 1
1 2 1
2 3 2
3 4 3
4 5 1
5 6 2
6 7 1
5 8 1
4 9 2
4 10 3
10 11 1
10 12 3

예제 출력 1

6 6

나머지 출력은 생략한다.

풀이

Python

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

n,r = map(int,input().rstrip().split())
graph = [[] for _ in range(n+1)]

for _ in range(n-1):
    a,b,c = map(int,input().rstrip().split())
    graph[a].append((b,c))
    graph[b].append((a,c))


ans =[0,0]

def dfs(u,p,sum,flag):
    if flag == 0: ans[0] = sum # 기가 노드까지의 간선 길이의 합
    else: ans[1] = max(ans[1],sum) # 긴 가지의 길이
    # root가 아닌데 인접노드가 2개보다 많으면, 자식이 두개 -> giga 
    # root인데 인접 노드가 2개 이상이면 ->  giga
    if flag==0 and len(graph[u]) > 2 -int(u==r): 
        flag,sum = 1, 0
    for v,w in graph[u]:
        if v== p: continue
        dfs(v,u,sum+w,flag)

dfs(r,r,0,0)

print(ans[0],ans[1])

Java

// 추후 작성 예정

정리

• flag를 통해서 0이면 기가 노드 까지의 간선 길이의 합을 구해주고, 1이면 리프노드를 돌면서 가장 긴 가지의 길이를 구한다.
• 이 부분은 root가 아닌데 인접노드가 2개보다 많으면, 자식이 두개 -> giga
  root인데 인접 노드가 2개 이상이면 -> giga를 의미한다.

  if flag==0 and len(graph[u]) > 2 -int(u==r):