[백준 20924번] 트리의 기둥과 가지 (python)

문제

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

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

마이크로는 트리의 기둥과 가지를 분류하기 위해 기가 노드를 추가로 정의하였다.

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

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

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

• 트리의 기둥은 루트 노드에서부터 기가 노드까지다. 위 그림에서 기둥은 1−2−3−4 이다.
  기둥의 길이는 기둥의 간선 길이의 합인 1+2+3=6 이 된다.
• 트리의 가지는 기가 노드에서부터 임의의 리프 노드까지다. 위 그림에서 가지는 4−5−6−7, 4−5−8, 4−9, 4−10−11, 4−10−12 총 5개가 있다.
  가지의 길이는 가지의 간선 길이의 합이다. 다행히도 가장 긴 가지의 길이 하나만 기재하면 된다. 4−10−12 가지가 간선 길이의 합 3+3=6 으로 가장 긴 가지이다.

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

 

기록

(트리 5일차) 풀고 바로바로 블로그 써야겠다. 푼 지 7시간밖에 안됐는데 금방 잊혀지는 듯. 생각해보니 양방향으로 edge정보 저장하다보니까 탐색하면서 루트로 다시 돌아가는 문제가 있었던 것 같다. 다시 못가게 하기위해 루트에서 노드로 내려갈때마다 반대 edge정보를 지워버렸던 것 같은데 이 방법이 좋은건진 잘 모르겠다! 일단 이렇게 풀고 나중에 더 공부해서 다시 봐봐야겠다.

 

코드

from sys import stdin, setrecursionlimit
from collections import defaultdict
setrecursionlimit(10**9)

def get_maxbranch(tree, root):
    if root not in tree : return 0

    maxbranch = 0
    for node, w in tree[root].items():
        del tree[node][root]
        branch = w + get_maxbranch(tree, node)
        if branch > maxbranch :
            maxbranch = branch
    return maxbranch

# 변수초기화
N, R = map(int, stdin.readline().split())
tree = defaultdict(dict)
for _ in range(N-1):
    a, b, w = map(int, stdin.readline().split())
    tree[a][b] = w
    tree[b][a] = w

# 기가노드까지의 기둥 길이 찾기
giganode = R
gigalen = 0
while len(tree[giganode])==1:
    node, w = list(tree[giganode].items())[0]
    del tree[node][giganode]
    gigalen += w
    giganode = node

# 가장 긴 가지 길이 찾기
maxbranch = get_maxbranch(tree, giganode)

print('{} {}'.format(gigalen, maxbranch))

1. 변수 초기화

 

2. 루트부터 기가노드까지의 기둥 길이 찾기

루트부터 자식노드로 가면서 자식노드가 2개 이상인 노드 만나면 멈추고 기가노드로 저장했다.

 

3. 기가노드부터 재귀적으로 돌면서 긴 가지 길이 찾기

get_maxbranch 함수는 leaf 노드부터 현재 노드까지의 최댓값 반환하는 재귀함수이다. base case는 leaf노드일 때 0 반환하는 것.