[BaekJoon] 1967 트리의 지름 (Java)

1.  문제 링크

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

2.  문제

요약

• 트리는 사이클이 없는 무방향 그래프이고 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 됩니다.
• 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것인데 이럴 때 트리의 모든 노드들은 그 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 됩니다.
• 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 하는데, 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말합니다.
• 트리의 노드는 1부터 n까지 번호가 매겨져 있습니다.
• 입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 10,000보다 작거나 같은 노드의 개수 n이 주어지고, 두 번째 줄부터 n - 1개의 줄에 각 간선에 대한 정보가 주어집니다. 간선에 대한 정보는 세 개의 정수로 이루어져 있는데, 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고, 두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치를 나타냅니다.
  • 간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼저 입력됩니다.
  • 루트 노드의 번호는 항상 1이라고 가정하며, 간선의 가중치는 100보다 크지 않은 양의 정수입니다.
• 출력: 첫 번째 줄에 트리의 지름을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int n, max = Integer.MIN_VALUE;
	static ArrayList<Edge>[] map;
	static boolean[] visited;
	static void input() {
		Reader scanner = new Reader();
		n = scanner.nextInt();
		map = new ArrayList[n + 1];
		for(int i = 1; i <= n; i++) map[i] = new ArrayList<Edge>();
		visited = new boolean[n + 1];
		for(int edge = 0; edge < n - 1; edge++) {
			int parent = scanner.nextInt();
			int child = scanner.nextInt();
			int weight = scanner.nextInt();
			map[parent].add(new Edge(child, weight));
			map[child].add(new Edge(parent, weight));
		}
	}
	
	static void solution() {
		for(int i = 1; i <= n; i++) {
			visited = new boolean[n + 1];
			visited[i] = true;
			dfs(i, 0);
		}
		System.out.println(max);
	}
	
	static void dfs(int num, int weight) {
		for(Edge e : map[num]) {
			if(!visited[e.vertex]) {
				visited[e.vertex] = true;
				dfs(e.vertex, weight + e.weight);
			}
		}
		max = Math.max(max, weight);
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {					
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
	
	static class Edge {
		int vertex, weight;
		public Edge(int vertex, int weight) {
			this.vertex = vertex;
			this.weight = weight;
		}
	}
}

4.  접근

• 주어진 간선에 대한 정보를 ArrayList 배열에 담고 각 노드에서 DFS를 이용해 해당 노드에서 가장 길게 이어지는 노드를 찾아 그 때의 길이들을 구해가고 그 중 가장 긴 길이가 트리의 지름이 됩니다.