[백준] 트리의 지름(1167)

문제

[백준] 트리의 지름(1167)

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

입력

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

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

출력

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

해설

처음엔 인접리스트와 DFS를 적용해 풀이하려 했으나 시간초과가 발생했다.
모든 정점에서 가장 먼 정점을 찾는 부분이 문제임을 깨닫고,
임의의 정점을 하나 정해 가장 먼 정점을 찾고, 다시 그 정점을 기준으로 가장 먼 정점을 찾도록 구현하였다.

풀이

import java.util.*;

import java.io.*;

public class Main {
	static int n;
	static List<Edge>[] graph;
	static int[] dist;

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

		n = Integer.parseInt(br.readLine());

		graph = new ArrayList[n + 1];

		for (int i = 0; i <= n; i++) {
			graph[i] = new ArrayList<>();
		}

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");

			int v = Integer.parseInt(st.nextToken());

			while (true) {
				int u = Integer.parseInt(st.nextToken());

				if (u == -1)
					break;

				int cost = Integer.parseInt(st.nextToken());

				graph[v].add(new Edge(u, cost));
			}
		}

		dist = new int[n + 1];
		
		bfs(1);
		
		int max = 0, max_idx = 0;
		
		for (int i = 1; i <= n; i++) {
			if(max < dist[i]) {
				max = dist[i];
				max_idx = i;
			}
		}
		
		Arrays.fill(dist, 0);
		
		bfs(max_idx);
		
		max = 0;
		
		for (int i = 1; i <= n; i++) {
			if(max < dist[i]) {
				max = dist[i];
			}
		}
		
		System.out.println(max);
	}

	public static void bfs(int v) {
		Queue<Integer> queue = new LinkedList<>();
		boolean[] visited = new boolean[n + 1];

		queue.add(v);
		visited[v] = true;

		while (!queue.isEmpty()) {
			int u = queue.poll();

			for (Edge edge : graph[u]) {
				if (!visited[edge.v]) {
					visited[edge.v] = true;
					queue.add(edge.v);
					dist[edge.v] = dist[u] + edge.cost;
				}
			}
		}
	}

	public static class Edge {
		int v, cost;

		public Edge(int v, int cost) {
			this.v = v;
			this.cost = cost;
		}
	}
}