[BOJ] 1967 / 트리의 지름 / Python 파이썬

[BOJ] 1967 / 트리의 지름 / Python 파이썬

[BOJ] 1967 / 트리의 지름 / Python 파이썬

https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

 

풀이

전날 풀었던 [BOJ] 1167 / 트리의 지름 / Python 파이썬 문제와 같이 Tree 의 지름을 구하는 문제이다.

 

다시 복습하자면,

 

• Tree 의 지름 : 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로

 

• 선형 시간내에 Tree 의 지름을 구하는 Algorithm

1. 트리에서 임의의 정점 xx를 잡는다. 
2. 정점 xx에서 가장 먼 정점 yy를 찾는다
3. 정점 yy에서 가장 먼 정점 zz를 찾는다.

 

import sys
from collections import deque


def BFS(start, finish=0):
    global N

    dq = deque()
    dq.append((start, 0))

    visited = [0] * (N+1)

    res = 0
    maxNode = 0

    while dq:
        f, add = dq.popleft()
        visited[f] = 1

        if finish and f == finish:
            return add

        for info in tree[f]:
            if visited[info[0]]:
                continue

            if res < add+info[1]:
                res = add + info[1]
                maxNode = info[0]
            dq.append((info[0], add+info[1]))

    return maxNode


input = sys.stdin.readline

N = int(input())
tree = [[] for _ in range(N+1)]

for _ in range(N-1):
    r, c, l = map(int, input().split())
    tree[r].append((c, l))
    tree[c].append((r, l))

v = BFS(1)
e = BFS(v)

print(BFS(v, e))

 

 

---

참고 블로그

https://blog.myungwoo.kr/112

트리의 지름 구하기