[백준] 1167 - 트리의 지름

[문제링크]

1167번: 트리의 지름

 

0. 1967번 문제와 거의 동일한 풀이 (링크)

 

1. 트리의 모든 노드를 거치며 최댓값을 찾으므로, 시작점의 위치는 아무거나 선택해도 상관 없다

 

2. 부모-자식 관계를 확인하기 힘드므로 boolean배열을 유지해 방문 노드의 재방문을 막는다

 

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));
		
		N = pint(br.readLine());
		isV=new boolean[N+1];
		graph=new ArrayList<>();
		max=0;
		
		for (int i = 0; i <= N; i++) {
			graph.add(new ArrayList<>());
		}
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int V = pint(st.nextToken());
			int node=0;
			while( (node=pint(st.nextToken()))!=-1 ) {
				int cost = pint(st.nextToken());
				graph.get(V).add(new int[] {node,cost});
			}
		}

		rec(1);
		System.out.println(max);
		
	}
	static int N, max;
	static boolean[]isV;
	static ArrayList<ArrayList<int[]>>graph;
	
	static int rec(int node) {
		isV[node]=true;
		int fst=0,snd=0;
		
		for (int i = 0; i < graph.get(node).size(); i++) {
			int[] next = graph.get(node).get(i);
			//미방문이면
			int temp=0;
			if(!isV[ next[0] ]) {
				temp = next[1] + rec( next[0] );
			}

			if(fst<temp) {
				snd=fst;
				fst=temp;
			}else if(snd<temp) {
				snd=temp;
			}
		}
		
		max = Math.max(max, fst+snd);
		return fst;
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면