[백준] 19581. 두 번째 트리의 지름 (JAVA)

📏 두 번째 트리의 지름

 

별 거 아닌데 이상한 개념에 사로잡혀서 헤맸어 . .

 

---

문제

트리에 N개의 정점이 있고, 각 정점 별로 1부터 N까지의 번호가 붙어있다.

 

트리에서 가장 먼 두 정점 간의 거리를 트리의 지름이라고 한다. 트리의 지름을 구하는 문제는 너무 많기 때문에 우리는 두 번째 트리의 지름을 구하려고 한다.

 

두 번째 트리의 지름은 무엇이냐? 바로 두 번째로 가장 먼 두 정점 간의 거리를 의미한다. (두 번째 트리의 지름은 트리의 지름과 같을 수 있다.)

 

바로 두 번째 트리의 지름을 구해보자.

 

입력

첫 번째 줄에는 정점의 개수 N(3 ≤ N ≤ 100,000)이 들어온다.

 

둘째 줄부터 N번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수와 두 번째 정수는 간선과 연결된 정점 번호를 나타내고, 세 번째 정수는 간선의 가중치를 나타낸다. 간선의 가중치는 20,000 이하의 자연수이다.

 

출력

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

 

---

🔑 IDEA 

트리의 지름을 구하는 방법은 다음과 같다.

1. 임의의 노드로부터 가장 먼 노드 A를 찾는다. 
2. 노드 A로부터 가장 먼 노드 B를 찾아 A-B 간의 거리를 구하면 트리의 지름이다.  

그런데 이 문제의 경우 두 번째 트리의 지름을 구해야 한다. 

나는 처음에 이 두 번째 트리의 지름이란 이 A-B에서 Math.max(A를 뺐을 때 거리, B를 뺐을 때 거리) 라고 생각했다..  ㅡ ㅡ

 

근데 그게 아니고, 

Math.max(B를 제외하고 A로부터 가장 먼 노드까지의 거리, A를 제외하고 B로부터 가장 먼 노드까지의 거리)

이렇게 접근해야 한다.

 

그래서, getFarthest() 메서드의 인자에 'except' 라는 인자를 전달하여 

가장 먼 노드를 찾을 때 except 노드를 무시할 수 있도록 해준다. 

 

 

💡  나의 풀이

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Node {
	int val;
	int weight;

	Node(int val, int weight) {
		this.val = val;
		this.weight = weight;
	}
}

class Main {
	static int N;
	static List<Node>[] edges;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		edges = new ArrayList[N+1];

		for(int i=1; i<=N; i++) edges[i] = new ArrayList<>();
		for(int i=0; i<N-1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			if(!st.hasMoreTokens()) break;
			int n1 = Integer.parseInt(st.nextToken());
			int n2 = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			edges[n1].add(new Node(n2, w));
			edges[n2].add(new Node(n1, w));
		}

		Node endPoint1 = getFarthest(1,0);
		Node endPoint2 = getFarthest(endPoint1.val, 0);
		int dist1 = getFarthest(endPoint1.val, endPoint2.val).weight;
		int dist2 = getFarthest(endPoint2.val, endPoint1.val).weight;

		System.out.println(Math.max(dist1, dist2));

	}

	private static Node getFarthest(int start, int except) {
		Queue<Node> queue = new LinkedList<>();
		boolean[] visited = new boolean[N+1];
		Node farthest = new Node(start, 0);

		queue.offer(farthest);

		while(!queue.isEmpty()) {
			Node cur = queue.poll();
			visited[cur.val] = true;

			if(cur.weight > farthest.weight && cur.val != except)
				farthest = cur;

			for(Node next: edges[cur.val]) {
				if(visited[next.val]) continue;
				visited[next.val] = true;
				queue.offer(new Node(next.val, cur.weight + next.weight));
			}
		}
		return farthest;
	}
}

 

 

---

 

19581번: 두 번째 트리의 지름