[Gold4-JAVA] 백준 1967 - 트리의 지름

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

1967번: 트리의 지름

 

 

🤔 문제 풀이

그래프 탐색 문제인 트리의 지름 문제이다.

트리의 연결 정보들 중에서 한 정점에서 다른 정점까지의 거리가 가장 긴 것을 찾으면 되는 문제다.

 

모든 정점에 대한 연결 정보를 저장하기 위해 Node 클래스를 생성하여 정점과 가중치 정보를 저장하고

이를 ArrayList에 저장하였다. 모든 정점 중, 한 start 정점에서 다른 모든 정점을 이동하며

start정점의 최대 길이를 갱신해주고 마지막에 모든 노드의 길이 정보에서 최대 값을 찾는 방식으로 풀었다.

 

🚨CODE

package ps;

import java.io.*;
import java.util.*;

public class Main {
	static boolean[] visit;
	static int[] maxLen;
	static ArrayList<Node>[] graph;
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		graph = new ArrayList[n+1];
		maxLen = new int[n+1];
		visit = new boolean[n+1];
		
		for(int i = 1; i<=n; i++) {
			graph[i] = new ArrayList<>();
		}
		
		StringTokenizer st;
		for(int i = 0; i<n-1; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			
			graph[a].add(new Node(b, weight));
			graph[b].add(new Node(a, weight));
		}
		
		for(int i = 1; i<=n; i++) {
			dfs(i, i, 0);
			Arrays.fill(visit, false);
		}
		
		int result = 0;
		for(int diameter : maxLen) {
			result = Math.max(diameter, result);
		}
		
		System.out.println(result);
	}
	public static void dfs(int startNode, int curNode, int len) {
		visit[curNode] = true;
		maxLen[startNode] = Math.max(maxLen[startNode], len);
		
		for(Node n : graph[curNode]) {
			if(visit[n.value])
				continue;
			
			dfs(startNode, n.value, len+n.weight);
		}
	}

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