[백준 1967] 트리의 지름

문제

트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.

이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.

입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다.

트리의 노드는 1부터 n까지 번호가 매겨져 있다.

 

입력

파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고, 두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치를 나타낸다

 

출력

첫째 줄에 트리의 지름을 출력한다.

---

접근

트리의 지름은 가장 긴 경로를 갖는 두 노드를 찾는 것이다. 여기서 두 노드가 될 수 있는 것은 리프 노드와 루트 노드이다. 리프 노드 <-> 리프 노드 이거나 리프 노드 <-> 루트 노드 이다. 만약 리프 노드 <-> 내부 노드라고 한다고 하면 내부 노드는 2개 이상의 노드와 연결이 되어있다. 탐색을 진행하면 내부 노드와 연결된 다른 노드를 탐색하지 못하고 종료가 될 것이다.

따라서 가장 긴 경로가 될 수 있는 것은 위의 두 가지이다.

 

그렇다면 루트 노드와 리프 노드를 어떻게 구할까? (지금까지 이해한 것 정리 -> 나중에 수정될 수도 있음)

루트 노드에 따라서 트리의 구조가 달라진다. 그렇기 때문에 명확한 루트 노드를 구할 수 없다. 

따라서 임의의 루트 노드를 기준으로 가장 멀리있는 리프 노드를 구한다. 여기서 구한 리프 노드는 가장 먼 두 개의 노드 중 하나가 될 것이다. (이에 대한 증명은 아직 확실히 이해하지 못했다.)

실제로 첫 번째 예시를 토대로 모든 노드를 루트 노드로 구했을 때 가장 멀리떨어진 노드는 9번 또는 12번이 나왔다.

 

따라서 임의의 노드에서 가장 멀리 떨어진 노드를 찾고 다시 해당 노드에서 멀리 떨어진 노드의 거리를 구한다.

 

구현

구현은 1167번과 유사하게 하였다.

import sys
from _collections import deque

input = sys.stdin.readline

def bfs(start):
    dist = [-1] * N
    dist[start] = 0
    q = deque()
    q.append(start)
    result = [0, 0] # 가장 먼 노드와 거리
    while q:
        parent = q.popleft()

        for child, weight in tree[parent]:
            if dist[child] == -1:
                dist[child] = dist[parent] + weight
                q.append(child)
                if dist[child] > result[1]:
                    result[0] = child
                    result[1] = dist[child]

    return result

N = int(input())
tree = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, weight = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append([b, weight])
    tree[b].append([a, weight])

for start in range(N):
    node, dist = bfs(start)
    print(start, ':',node, dist)
    node, dist = bfs(node)