b_트리의 지름_1967

문제

트리에서 직선을만들려고할때 가장 길이가 긴것이몇인지
추후 자기노드를 통과하는 선을 지름이라고부르고
끝에서 자기노드까지를 반지름으로 표현예정

접근 : 밑부터 반지름들을 구해서 합하자

답 1(틀림)

자식 여부를 판별해서 자식이없는 leafnode부터 접근하느방법임
depth가 다른 leafnode가있을때 문제생김
자식노드다처리안됐는데 부모노드접근됨
ex ) answer has to be 13
input
5
1 2 3
1 3 3
2 4 5
2 5 7

import sys
import math
import heapq

NNum = int(sys.stdin.readline().strip())

parents = [None]* (NNum+1) # 자식입장에서 부모
sons = [[] for _ in range(NNum+1)] # 부모입장서자식
result = [0]  * (NNum+1)# 반
visited = [False] * (NNum+1)
output = -1

for _ in range(NNum-1):
    M,S,W=map(int,sys.stdin.readline().strip().split())
    parents[S]= M
    heapq.heappush(sons[M],(-W,S))


def findMaxLine():
    global parents,sons,result,visited,output
    empties = set([]) # leaf node
    for i in range(1,NNum+1):
        if len(sons[i]) < 1 and not visited[i]:
            empties.add(i)
            visited[i] = True
    if not empties:
        return

    print("leafnode",empties)
    filtered_moms = set([])
    # 각 leaf의 부모를 찾아
    for e in empties:
        if parents[e]:
            filtered_moms.add(parents[e])
    print("leafnode's mom",filtered_moms)
    if not filtered_moms:
        return

    # 각 부모의 최대 반지름과 지름을 구함
    for mom in filtered_moms:
        mysons= sons[mom]
        tmp = [] # 반, 지름
        while mysons and len(tmp)<2:
            w,s=heapq.heappop(mysons)
            if tmp:
                tmp.append(tmp[0]+result[s]-w)
            else:
                tmp.append(result[s]-w)
        print("노드의 최대 반지름과지름",mom,tmp)
        result[mom] = tmp[0]
        sons[mom] = []
        output = max(output,tmp[-1])
    return findMaxLine()
findMaxLine()
print(output)

답2(재귀 - 최대재귀깊이 초과)

https://dev-yyh.github.io/DataStructure/10
트리순회하는법찾다가 후위순회하면될거같다는 생각을함.
이미부모가 다처리된 자식노드를 돌 수있음
재귀를이용해서함 but 최대 재귀 깊이를 초과한다는 답을받음

import sys
import heapq

class Node:
    def __init__(self, data):
        self.data = data
        self.children = []


NNum = int(sys.stdin.readline().strip())
trees = [None]
weight = {}

for i in range(NNum):
    trees.append(Node(i+1))

# <span id="printtrees"></span>print(trees)
for _ in range(NNum-1):
    M,S,W=map(int,sys.stdin.readline().strip().split())
    trees[M].children.append(trees[S])
    weight[f"{M}-{S}"]=W

root = trees[1]
output = 0
# <span id="printweight"></span>print(weight)
def post_order_traversal(node):
    global output
    if node is None:
        return
    hq = []
    for child in node.children:
        pw = post_order_traversal(child)
        w = weight[f"{node.data}-{child.data}"]
        # print(node.data,"<-",child.data,":",pw+w)
        heapq.heappush(hq,-(pw+w))
    tmp = [output]
    try:
        w1 = heapq.heappop(hq)
        tmp.append(-w1)
        w2 = heapq.heappop(hq)
        tmp.append(-(w1+w2))
    except:
        pass
    output = max(tmp)
    # print(node.data,":",output)
    try:
        return tmp[1]
    except:
        return 0
    

post_order_traversal(root)
print(output)

답3(정답)

그래서 재귀를 while과 stack을 이용하여 구현함
재귀(콜백)은 스택으로 구현가능(컴터에서내부적으로도그렇게실행됨ㅋ)

import sys
import heapq

class Node:
    def __init__(self, data):
        self.data = data
        self.children = []

NNum = int(sys.stdin.readline().strip())
trees = [None]
weight = {}

for i in range(NNum):
    trees.append(Node(i+1))

for _ in range(NNum-1):
    M,S,W = map(int, sys.stdin.readline().strip().split())
    trees[M].children.append(trees[S])
    weight[f"{M}-{S}"] = W

root = trees[1]
output = 0

def post_order_iterative(root):
    global output
    stack = [(root, 0, [])]  # (현재노드, 다음 방문할 자식 인덱스, 자식별 반환값 리스트)
    while stack:
        node, idx, results = stack.pop()
        if idx < len(node.children):
            stack.append((node, idx + 1, results))
            stack.append((node.children[idx], 0, []))
        else:
            hq = []
            for i, child_val in enumerate(results):
                w = weight[f"{node.data}-{node.children[i].data}"]
                heapq.heappush(hq, -(child_val + w))
            tmp = [output]
            try:
                w1 = heapq.heappop(hq)
                tmp.append(-w1)
                w2 = heapq.heappop(hq)
                tmp.append(-(w1 + w2))
            except:
                pass
            output = max(tmp)
            ret_val = tmp[1] if len(tmp) > 1 else 0

            if stack:
                stack[-1][2].append(ret_val)

post_order_iterative(root)
print(output)