문제

트리의 지름

풀이

방향이 없는 트리이기 때문에 그래프이다. 사이클도 없다고 하니 그래프에서 가중치가 가장 높은 곳에 있는 노드를 찾아서 그 노드를 거치는 가장 긴 길이를 찾아주면 되는 문제이다.

// 그래프를 담는다
ArrayList<Node>[] tree = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
	tree[i] = new ArrayList<>();
}

// 그래프를 그린다
for (int i = 0; i < n; i++) {
	...
	tree[parent].add(new Node(child, weight));
    tree[child].add(new Node(parent, weight));
}

이 부분은 그래프 문제에서 자주 사용되는 부분인데 조금 헷갈렸다. 그래프를 오래간만에 그려봄. ㅠ

private static void dfs(int current, int weight) {
	if (answer < weight) {
    	answer = weight;
       	endNode = current; 
    }
    
    visited = new boolean[n + 1];
    
    for (Node n : tree[current]) {
    	if (!visited[n.value]) {
        	dfs(n.value, n.weight + weight);
        }
    }
}

가중치가 가장 높은 노드를 찾기 위해서는 dfs의 가중치가 가장 높을때 노드를 찾아야 하기 때문에 endNode 변수를 두게 된 것이다.
그래서 가장 가중치가 큰 노드인endNode 를 포함하여 단말노드가 나올때까지 반복하여 가장 큰 값이 나오게 할수 있는 dfs를 또 사용해주면 된다

전체 코드

전체 코드