Tree 백준 알고리즘 자바 1167 ‘트리의 지름’ 문제풀이

Problem

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

Input 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 매겨져 있다고 생각한다) 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

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

Solution

루트에서 가장 멀리 있는 노드와, 그 노드에서 가장 멀리 있는 노드와의 거리를 구하는 문제이다. 이차원 배열을 사용하면 메모리 초과가 나오기때문에 class Node와 인접리스트를 이용하여 문제를 해결해야 한다.

• list[0].add(new Node(1, 0))으로 루트노드 1을 가리키는 노드의 리스트를 하나 만들었다.
• dfs를 사용하되 노드 간의 거리를 계속 더해주고 그것들의 최대값을 구하여 그때의 노드를 maxNode에 저장한다.
• 방문기록 visit[]을 초기화하고, maxNode와 max값 모두 초기화한다.
• maxNode로부터 시작하는 dfs를 실행하고 거리 간의 최대값을 구하여 출력한다.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
class Node {
	int node, dist;
	public Node(int node, int dist) {
		this.node = node;
		this.dist = dist;
	}
}
public class Main {
	static List<Node>[] list;
	static boolean[] visit;
	static Node maxNode;
	static int max = 0, n;
	
	private static Node dfs(Node v, int dist) {
		visit[v.node] = true;
		
		for(Node tmp : list[v.node]) {
			if(!visit[tmp.node]) dfs(tmp, dist + tmp.dist);
		}
		
		if(max < dist) {
			maxNode = v; max = dist;
		}
		return maxNode;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Node maxx; n = Integer.parseInt(br.readLine());
		
		list = new ArrayList[n+1]; visit = new boolean[n+1];
		for(int i = 0; i <= n; i++) list[i] = new ArrayList<>();
		
		list[0].add(new Node(1, 0));
		for(int i = 0; i < n; i++) {
			String[] tmp = br.readLine().split("\\s");
			int a = Integer.parseInt(tmp[0]), b = Integer.parseInt(tmp[1]), c = Integer.parseInt(tmp[2]);
			
			list[a].add(new Node(b, c)); list[b].add(new Node(a, c));
			for(int j = 3; j < tmp.length; j += 2) {
				if(tmp[j].equals("-1")) break;
				b = Integer.parseInt(tmp[j]); c = Integer.parseInt(tmp[j+1]);
				list[a].add(new Node(b, c)); list[b].add(new Node(a, c));
			}
		}
		
		maxx = dfs(list[0].get(0), 0); visit = new boolean[n+1]; maxNode = null; max = 0;
		dfs(maxx, 0);
		System.out.print(max);
	}
}