파이썬 알고리즘 258번 | [백준 20924번 트리의 기둥과 가지] - 다시 풀어내기

258. 트리의 기둥과 가지

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

<내 풀이>

<다른 분의 풀이>

출처 : 출처

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

def root_dfs(node,dis): # 기가 노드 찾는 dfs 
    if visited[node]:
        return
    visited[node] = 1
    count = 0
    nexts = -1
    distance = 0
    for next_node in tree[node]:
        if not visited[next_node]:
            count += 1
            nexts = next_node
            distance += tree[node][next_node]
    if count == 1:
        return root_dfs(nexts,dis+distance)
    else:
        return [node,dis]

def leaf_dfs(node,dis): # 리프노드 중 최대 길이 찾는 dfs 
    global leaf_dis
    visited[node] = True
    count = 0
    for next_node in tree[node]:
        if not visited[next_node]:
            leaf_dfs(next_node,dis+tree[node][next_node])
            count += 1
    if not count:
        leaf_dis = max(leaf_dis,dis)


n,r = map(int,input().split())
tree = [{} for _ in range(n+1)]
for _ in range(n-1):
    x,y,b = map(int,input().split())
    tree[x][y] = b 
    tree[y][x] = b

visited = [0 for _ in range(n+1)]
root_dis = root_dfs(r,0) 
# 기가노드 찾으면 그때까지의 길이가 기둥이지 

leaf_dis = 0
leaf_dfs(root_dis[0],0)
print(root_dis[1],leaf_dis)

<반성 점>

<배운 점>