백준 1167 트리의 지름

문제와 같이, 트리의 지름은 임의의 노드에서 가장 먼 노드를 찾는 것이다.

1. 트리의 지름

이것이 처음에 이해가지 않았지만 자료를 찾아보니 알 수 있었다.
한 마디로 정의하자면, 트리의 지름 = 끝 과 끝이다.

예를 들어, 아래와 같은 트리가 있다고 가정하자.

그랬을 경우, 임의의 노드를 1로 가정한 뒤 가장 먼 노드를 찾는다면 7 or 8이 될 것이다. (여기서는 8로 가정함)

위와 같이 1 에서 가장 먼 노드인 8을 구하기 위해서는 BFS를 한번 해줘야한다.

그 다음 다시 한번 BFS를 통해서 위와 같이 8 에서의 가장 먼 노드인 3 or 4를 찾을 수 있다.
즉, 2번의 BFS를 통해서 가장 먼 노드들 (3과 8)을 찾을 수 있다.

2. 백준 1167번 문제

두 번의 BFS를 통해 트리의 지름을 찾는 문제이다. 해당 문제에서는 거리가 주어지고, 거리에 따른 트리의 지름을 찾는 문제이다.

# 트리의 지름 = 트리에서 가장 긴 경로
# 백트래킹 같은 경우 가지치기가 핵심인데, 이 문제는 모든 경로를 찾아야 하므로 부적절함.
from collections import deque

def bfs(node, weight):
    visit = [0] * (v+1)
    visit[node] = 1
    que = deque()
    que.append((node, weight))

    far_node, far_weight = 0, 0

    while que:
        top_node, top_weight = que.popleft()

        for n, w in lis[top_node]:
            if not visit[n]:
                que.append((n, top_weight + w))
                visit[n] = 1

                if top_weight + w > far_weight:
                    far_weight = top_weight + w
                    far_node = n


    return far_node, far_weight


import sys
input = sys.stdin.readline

v = int(input())
lis = [[] for _ in range(v+1)]


for _ in range(v):
    st = list(map(int, input().split(" ")))
    node, st = st[0], st[1:-1]

    for i in range(0, len(st), 2):
        lis[node].append((st[i], st[i+1]))

first_end_node, first_end_weight = bfs(1, 0)
# print(first_end_node, first_end_weight)

second_end_node, second_end_weight = bfs(first_end_node, 0)
print(second_end_weight)

위와 같이 한번 BFS 한 결과 노드를 다시 BFS 하여서 정답을 찾아낼 수 있다.