[백준] 1967 : 트리의 지름 JAVA 풀이

 

모든 노드에 대해서 dfs를 수행하는 방법과,

루트 노드를 기준으로 dfs를 수행해서 가중치가 가장 큰 노드를 찾고,

그 노드부터 다시 dfs를 수행하는 두 가지의 방법으로 풀어보았다.

 

코드는 크게 다를 게 없지만 실행시간에서 큰 차이가 났다.

전자는 dfs를 2번만 수행하면 되지만 후자는 N-1번 수행해야 하니 당연하다.

import java.io.*;
import java.util.*;
public class Main {
	
	static class Node{
		int idx;
		int cnt;
		Node(int idx, int cnt){
			this.idx = idx;
			this.cnt = cnt;
		}
	}
	
	static boolean[] visit;
	static ArrayList<Node>[] list;
	static int max = 0;
	
	int answer = Integer.MIN_VALUE;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		list = new ArrayList[N+1];
		visit = new boolean[N+1];
		
		for(int i=0;i<=N;i++) {
			list[i] = new ArrayList<>();
		}
		
		for(int i=0;i<N-1;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			
			int parent = Integer.parseInt(st.nextToken());
			int child = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			
			list[parent].add(new Node(child, weight));
			list[child].add(new Node(parent, weight));
		}
		
		for(int i=1;i<=N;i++) {
			visit = new boolean[N+1];
			visit[i] = true;
			dfs(i, 0);
		}
		System.out.println(max);
	}
	
	static void dfs(int idx, int cnt) {
		
		for(Node n : list[idx]) {
			if(!visit[n.idx]) {
				visit[n.idx] = true;
				dfs(n.idx, cnt+n.cnt);
			}
		}
		max = (max<cnt)?cnt:max;
	}
}

 

import java.io.*;
import java.util.*;
public class Main {
	
	static class Node{
		int idx;
		int cnt;
		Node(int idx, int cnt){
			this.idx = idx;
			this.cnt = cnt;
		}
	}
	
	static boolean[] visit;
	static ArrayList<Node>[] list;
	static int max = 0;
	static int max_idx = 0;
	
	int answer = Integer.MIN_VALUE;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		list = new ArrayList[N+1];
		visit = new boolean[N+1];
		
		for(int i=0;i<=N;i++) {
			list[i] = new ArrayList<>();
		}
		
		for(int i=0;i<N-1;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			
			int parent = Integer.parseInt(st.nextToken());
			int child = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			
			list[parent].add(new Node(child, weight));
			list[child].add(new Node(parent, weight));
		}
		
		visit[1] = true;
		dfs(1,0);
		
		visit = new boolean[N+1];
		visit[max_idx] = true;
		dfs(max_idx, 0);
		System.out.println(max);
		
	}
	
	static void dfs(int idx, int cnt) {
		
		if(max<cnt) {
			max = cnt;
			max_idx = idx;
			
		}
		
		for(Node n : list[idx]) {
			if(!visit[n.idx]) {
				visit[n.idx] = true;
				dfs(n.idx, cnt+n.cnt);
			}
		}
		
	}
}