Name : 트리의 지름
No : 1967
URL : https://www.acmicpc.net/problem/1967
Start Time : 10:03
End Time : 10:48 (45m)
Result(Pass / Failed) : Pass
Algorithm: DFS
Calculating time complexity:
import java.util.*;
import java.io.*;
public class Main
{
static int n; // 노드 개수
static int answer = -1; // 최대 거리(트리의 지름)
static boolean[] visited; // 노드별로 최대거리 탐색할때 방문처리할 배열
//간선 정보
static class Edge{
int to; // 도착 노드
int weight; // 가중치
Edge(int to, int weight){
this.to = to;
this.weight = weight;
}
}
static void dfs(int now, List<List<Edge>> adj, int weight){
visited[now] = true; //지금 노드 방문 처리
answer = Math.max(answer, weight); // 매 노드마다 최대값(트리 지름) 업데이트
//지금 노드와 인접한 노드들을 전부 본다.
for(int i=0; i<adj.get(now).size(); i++) {
Edge edge = adj.get(now).get(i);
if (!visited[edge.to]) { //방문하지 않은 노드라면
dfs(edge.to, adj, weight + edge.weight); // 탐색
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//노드 개수 입력받기
n = Integer.parseInt(br.readLine());
// 인접리스트
List<List<Edge>> adj = new ArrayList<>();
// 초기화
for (int i = 0; i <= n; i++) {
adj.add(new ArrayList<>());
}
for(int i = 1; i<= n-1; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int f = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
// 양방향 그래프(트리)이기 때문에 둘다 연결해준다.
adj.get(f).add(new Edge(t, w));
adj.get(t).add(new Edge(f, w));
}
// 각 노드를 시작점으로해서, 최대 거리를 구한다.
for(int i=1; i<=n; i++){
visited = new boolean[n+1]; // 매 시작점마다 방문 노드 초기화
dfs(i, adj, 0);
}
System.out.println(answer);
}
}