문제링크: https://www.acmicpc.net/problem/1167

1. 아이디어💡

1.1. 문제분석

• 트리에서 가장 먼 두개의 노드의 거리를 구해야한다.
• 노드간에 거리가 주어진다.

1.2. 해결 방법

플로이드 와샬 알고리즘 사용해본 결과 -> 메모리 초과

모든 노드가 다른 모든 노드의 거리에 대한 정보를 저장하는 것은 공간 복잡도가 커짐

트리는 최소 간선 수를 가진다는 것을 이용, 거리 탐색할 때는 BFS 사용

1. 각 노드와 연결된 간선의 정보를 dictionary로 저장한다. 만약 입력이 다음과 같이 주어지면

5
1 3 2 -1
2 4 4 -1
3 1 2 4 3 -1
4 2 4 3 3 5 6 -1
5 4 6 -1

실제 노드번호는 (입력된 노드번호 - 1)로 저장되고 그 형태는 다음과 같다.

{2: 2}
{3: 4}
{0: 2, 3: 3}
{1: 4, 2: 3, 4: 6}
{3: 6}

2. 임의의 단말 노드를 하나 정해서 다른 모든 노드에 대한 거리 탐색을 해서 가장 먼 거리의 노드를 찾는다. ex) 0번 노드에서 탐색하면 4번노드까지 11의 최대 거리를 가진다.
3. 찾은 최대 거리를 가지는 노드에서 다시 탐색을 해서 찾은 최대거리가 트리의 지름이다. ex) 4번 노드에서 다시 탐색하면 0번노드까지 11의 최대거리를 가진다.

2. 코드

import sys
from collections import deque
input = sys.stdin.readline

# 입력 받기
N = int(input())
table = [{} for _ in range(N)]
for _ in range(N):
    a = list(map(int, input().split()))[:-1]
    for i in range(1, len(a), 2):
        table[a[0] - 1][a[i] - 1] = a[i + 1]
    if len(a) == 3: # 트리의 말단 노드 leaf에 저장
        leaf = a[0] - 1

q = deque()
max_dst = 0 # 결과 값 저장하는 변수
for _ in range(2):
    # 큐에 (노드번호, 간선 가중치) 삽입
    q.append((list(table[leaf].keys())[0], list(table[leaf].values())[0]))

    # visited 초기화
    visited = [-1] * N
    visited[leaf] = 0
    visited[q[0][0]] = q[0][1]
    while q: # BFS로 다른 모든 노드로의 거리 계산
        a = q.popleft()
        for i in table[a[0]]:
            if visited[i] == -1 or visited[i] > table[a[0]][i] + a[1]:
                q.append((i, table[a[0]][i] + a[1]))
                visited[i] = q[-1][1]
    
    # 가장 거리가 먼 노드의 인덱스와 거리값을 저장
    for i in range(len(visited)):
        if visited[i] > max_dst:
            max_dst = visited[i]
            leaf = i
print(max_dst)