[Baekjoon] 1167번 : 트리의 지름

1. 문제

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

• 트리, DFS, BFS 문제

// 문제
트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다.
트리의 지름을 구하는 프로그램을 작성하시오.

// 입력
트리가 입력으로 주어진다.
먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)
둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다.
정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고,
이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데,
하나는 정점번호, 다른 하나는 그 정점까지의 거리이다.
예를 들어 네 번째 줄의 경우
정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고,
정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다.
각 줄의 마지막에는 -1이 입력으로 주어진다.
주어지는 거리는 모두 10,000 이하의 자연수이다.

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

// 예제 입력 1
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
11

2. 핵심 아이디어

• 임의의 노드 x에서 가장 먼 노드 y를 찾고, y에서 가장 먼 노드 z를 찾음
• 그 후 y와 z 노드 사이의 길이를 찾으면 트리의 지름을 구할 수 있음

3. Python 문제풀이

import sys
input = sys.stdin.readline

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

for i in range(v) :
  p = list(map(int, input().split()))
  p_len = len(p)
  for i in range(1, p_len//2) :
    graph[p[0]].append([p[2*i-1], p[2*i]])

arr = [0 for _ in range(v+1)]

def dfs(s, m, r) :
  for e, d in m[s] :
    if r[e] == 0 :
      r[e] = r[s] + d
      dfs(e, m, r)

dfs(1, graph, arr)
arr[1] = 0

tmp = 0
idx = 0

for i in range(len(arr)) :
  if tmp < arr[i] :
    tmp = arr[i]
    idx = i

result = [0 for _ in range(v+1)]
dfs(idx, graph, result)
result[idx] = 0
print(max(result))

4. Java 문제풀이