공부 기록

트리의 지름: 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것

트리의 지름이라면.. 저번에 풀었던 문제를 함께 보면 좋다.

2020/12/20 - [알고리즘 공부/programmers] - Programmers 68937: 트리 트리오 중간값

어떤 트리의 지름을 구하는 방법을 예시를 통해 보자.

1. 먼저 임의의 점(1)부터 순회를 시작하여 가장 먼 거리에 있는 점 5를 찾는다.

2. 가장 먼 점 5에서 다시 순회를 하면서 가장 먼 거리에 있는 점은 2이며, 5~2=11이 트리의 지름이 된다.

이러한 풀이를 이용하면 모든 점에 대해 가장 먼 거리를 구하지 않아도 되고, 시간복잡도는 O(N)으로 줄어든다. 풀이는 아래와 같다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int v = in.nextInt();
		LinkedList<Node> connections[] = new LinkedList[v + 1];
		for (int i = 1; i <= v; i++) {
			int start = in.nextInt();
			connections[start] = new LinkedList<Node>();
			
			while (true) {
				int end = in.nextInt();
				if (end == -1) {
					break;
				}
				int length = in.nextInt();

				connections[start].add(new Node(end, length));
			}
		}

		System.out.println(findTreeRadius(1, connections, true, v));
	}

	public static int findTreeRadius(int start, LinkedList<Node> connections[], boolean isFirstCycle, int n) {
		boolean[] isVisited = new boolean[n + 1];

		Queue<Node> queue = new LinkedList<Node>();
		queue.add(new Node(start, 0));
		isVisited[start] = true;

		int maxNode = start;
		int maxLength = 0;
		while (!queue.isEmpty()) {
			Node now = queue.poll();

			if (maxLength < now.length) {
				maxLength = now.length;
				maxNode = now.name;
			}

			for (Node next : connections[now.name]) {
				if (!isVisited[next.name]) {
					queue.add(new Node(next.name, now.length + next.length));
					isVisited[next.name] = true;
				}
			}
		}

		if (isFirstCycle) {
			return findTreeRadius(maxNode, connections, false, n);
		}
		return maxLength;
	}
}

class Node {
	int name;
	int length;

	public Node(int name, int length) {
		this.name = name;
		this.length = length;
	}

	@Override
	public String toString() {
		return "(" + name + ", " + length + ")";
	}
}