난이도 : 골드 2
유형 : 트리
https://www.acmicpc.net/problem/1167

문제

트리의 지름을 구하는 프로그램을 만드는 문제이다.

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리중 가장 긴 것을 말한다.

해결 아이디어

트리의 지름을 구할 때는 보통 두 번의 DFS/BFS를 사용한다.

1. 임의의 한 정점에서 시작해 가장 먼 정점 A를 찾는다.

2. A에서 다시 DFS/BFS를 돌려 가장 먼 정점 B를 찾는다.

3. A와 B 사이의 거리가 트리의 지름이다.

해답 및 풀이

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

V = int(input())
graph = [[] for _ in range(V+1)]

for _ in range(V):
    data = list(map(int,input().split()))
    u = data[0]
    idx = 1
    while data[idx] != -1:
        v = data[idx] # 노드 번호
        w = data[idx+1] #거리
        graph[u].append((v, w))
        idx += 2 # 2개 뒤 => 다음 노드번호와 거리 탐색

# bfs 함수
def bfs(start):
    visited = [-1] * (V+1) # start부터 각 노드까지의 거리 저장, -1은 아직 방문 X 의미
    q = deque()
    q.append(start)
    visited[start] = 0 # 시작녿브ㅜ터 시작노드 까지의 거리는 0

    while q:
        now = q.popleft()
        for nxt, cost in graph[now]:
            if visited[nxt] == -1:
                visited[nxt] = visited[now] + cost
                q.append(nxt)

    
    # visited 배열에서 가장 먼 거리와 그 노드 번호를 구한다.
    max_dist = max(visited)
    max_node = visited.index(max_dist)
    return max_node, max_dist

# 두번의 BFS를 통해 트리의 지름 구하기.
a, _ = bfs(1) # bfs함수의 return 문이 max_node, max_dist 이렇게 되어있으면 (max_node, max_dist) 이렇게 튜플형식으로 저장되어있음.
# 첫번쨰 bfs에서는 노드번호만 필요하고 거리를 필요하지 않기에 거리는 _ 로 받아준다. _ 기호는 필요없는 값을 받을 때 쓰는 파이썬 관례이다.
b, diameter = bfs(a) # a 에서 가장 먼 노드 b까지의 거리 = 지름
print(diameter)

트리의 지름을 구하라?
-> BFS or DFS 두번 써서 가장 먼 노드까지의 거리를 구하자.