[백준] 1967 - 트리의 지름

[문제링크]

1967번: 트리의 지름

 

0. 트리의 차수가 2 이상 커지지 않는다는 글이 있지만, 2 이상의 자식도 가정하고 작성

  - 관련글 (링크)

 

1. A노드가 root인 트리의 지름은?

  - 자식 노드 B,C,D가 있을 때, 각 자식 트리의 최대 깊이들 중 1, 2순위의 합이다

 

2. 자식 서브트리의 최대 깊이는? 재귀를 통해 최대 깊이만 반환토록 해 구한다

  - 자식이 없으면 0을 반환

  - 자식의 최대 깊이 + root로부터의 cost = 최대 깊이

 

3. 자식들을 순회하며 길이를 구하고, 1위와 2위를 구한 후 1+2의 결과로 지름을 갱신

  - 1순위만을 반환해 부모 트리의 연산에 이용한다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());
		graph = new ArrayList<>();
		for (int i = 0; i <= N; i++) {
			graph.add(new ArrayList<>());
		}
		
		for (int i = 0; i < N-1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = pint(st.nextToken());
			int m = pint(st.nextToken());
			int c = pint(st.nextToken());
			
			graph.get(n).add(new int[] {m,c});
		}
		
		rec(1);
		System.out.println(max);
	}
	static int max=0;
	static ArrayList<ArrayList<int[]>>graph;
	
	static int rec(int node) {
		int fstMin=0, sndMin=0;
		
		for (int i = 0; i < graph.get(node).size(); i++) {
			int[] cur = graph.get(node).get(i);
			
			int temp = cur[1] + rec(cur[0]);
			
			if(fstMin<temp) {
				sndMin=fstMin;
				fstMin=temp;
			}
			else if(sndMin<temp) {
				sndMin=temp;
			}
		}
		max=Math.max(max, fstMin+sndMin);
		return fstMin;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면