문제

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

---

입력

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

---

출력

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

---

풀이

제한조건

• (1 ≤ n ≤ 10,000)
• 간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼저 입력된다.
• 루트 노드의 번호는 항상 1이라고 가정하며, 간선의 가중치는 100보다 크지 않은 양의 정수이다.

접근방법

단순 탐색
단순 탐색으로 해결할 수 있다.

하지만 완전 탐색을 수행할 경우, 시간초과가 발생한다.
조금 더 적은 탐색을 통해 계산할 방법을 생각해야한다.

트리의 지름을 구하는 문제는 잘 알려진 문제로 단순한 방법으로 구할 수 있다.
여기서는 증명은 하지 않는다.
(문제를 많이 풀어야 하는이유.. 안 풀어보면 알 수가 없다..!)

1. 트리 위 임의의 한 점으로 부터 가장 먼 지점(A)을 찾는다.
2. 1에서 구한 가장 먼 지점(A)에서 가장 먼 지점(B)를 찾는다.
3. A-B 구간이 가장 긴 구간이다.

1. 트리 위 임의의 한 점으로 부터 가장 먼 지점(A)을 찾는다.
임의의 한 점으로 아무것이나 두어도 상관없다.
하지만, 문제에서 루트가 1로 주어졌으니 1에서부터 탐색을 하며, 가장 먼 노드를 찾는다.

탐색은 DFS와 BFS 어떤것이든 상관없다.

2. 1에서 구한 가장 먼 지점(A)에서 가장 먼 지점(B)를 찾는다.
방문배열과 기타 탐색에 필요한 변수들을 초기화 해주고, 가장 먼지점에서부터 다시 탐색을 시작하여 가장 먼 지점을 찾는다.

주의할 점은 아래 2가지이다.

• N이 1인 경우
• 시작점을 방문처리 해줄 것.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
	static class Node {
		int to;
		int weight;

		Node(int a, int b) {
			to = a;
			weight = b;
		}
	}

	static int N;
	static List<Node>[] list;
	static boolean[] visit;
	static Node maxNode;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		N = stoi(in.readLine());
		list = new List[N + 1];
		for (int i = 0; i <= N; ++i)
			list[i] = new ArrayList<>();

		// 그래프 형식으로 입력을 받아둔다.
		for (int i = 0; i < N - 1; ++i) {
			String[] inputs = in.readLine().split(" ");
			int a = stoi(inputs[0]);
			int b = stoi(inputs[1]);
			int c = stoi(inputs[2]);
			list[a].add(new Node(b, c));
			list[b].add(new Node(a, c));
		}

		// 1. 임의의 점에서 가장 먼 지점 찾기
		maxNode = new Node(0, 0);
		visit = new boolean[N + 1];
		visit[1] = true;
		dfs(1, 0);
	
		// 2. 1에서 찾은 가장 먼지점에서, 다시 가장 먼 지점을 찾아본다.
        int start = maxNode.to;
		maxNode.to = 0;
		maxNode.weight = 0;
		visit = new boolean[N + 1];
		visit[start] = true;
		dfs(start, 0);
        
        // 3. 직전에 구한 가장 먼 거리가 지름이다.
		System.out.println(maxNode.weight);
	}

	private static void dfs(int start, int cost) {
		if (cost > maxNode.weight) {
			maxNode.weight = cost;
			maxNode.to = start;
		}

		for (int i = 0; i < list[start].size(); i++) {
			Node next = list[start].get(i);
			if (!visit[next.to]) {
				visit[next.to] = true;
				dfs(next.to, cost + next.weight);
			}
		}
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}