[백준 파이썬] 1967 트리의 지름

📌문제 출처

백준 단계별 문제풀이 : 트리
https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

❓ 문제

 

📗 풀이 코드

'''
임의 노드(1)에서 가장 멀리 떨어진 노드가 지름의 한 점이므로
그 노드로부터 가장 멀리 떨어진 노드까지의 거리를 구하자.
출발 노드로부터 가장 멀리 떨어진 노드와 그 거리를 반환하는 BFS함수를 만들자.
'''
from collections import defaultdict, deque
input = open(0).readline

def solution():
    # 변수 선언
    n = int(input())
    tree = defaultdict(list) # 개별 노드로부터 이어진 노드들의 집합
    for _ in range(n-1):
        a,b,w = map(int, input().split()) # a,b는 노드, w는 가중치
        tree[a].append([b,w])
        tree[b].append([a,w])
    # bfs 함수 : True면 노드를, False면 거리를 반환
    def bfs(sta,flag=True):
        visited = defaultdict(int) # 노드별 방문 확인
        max_node = max_dist = 0 # 출발 노드로부터 가장 멀리 떨어진 노드, 노드까지의 거리
        stack = deque([[0,sta]]) # [노드 도달 가중치 합, 도달 노드]
        while stack :
            cur_dist, cur_node = stack.popleft()
            visited[cur_node] = 1 # 현재 노드 방문 체크
            if max_dist < cur_dist : # 최대 거리 갱신
                max_dist, max_node = cur_dist, cur_node
            for new_node,new_dist in tree[cur_node]: # 현재 노드와 이어진 노드 하나씩 확인
                if not visited[new_node] : # 방문한 적 없다면
                    visited[new_node] = 1 # 현재 거리 + 도달 거리
                    stack.append([cur_dist+new_dist,new_node]) # bfs에 추가
        if flag : # 노드 반환
            return max_node
        return max_dist # 거리 반환
    return bfs(bfs(1),False) # 임의 노드(1)로부터 가장 먼 노드로부터 가장 먼 노드까지 거리 반환
if __name__ == '__main__':
    print(solution())