#백준_1967 트리의 지름 - Java

 

https://ukyonge.tistory.com/17?category=870877

#백준_1167 트리의 지름 - Java

 

 

#위와 같은 방식으로 접근하여 풀 수있는 문제. 개인적으로는 1967번 문제를 먼저 풀고, 1167번 문제를 푸는 것을 추천.

지름을 구하는 법을 알지 못하면 한참동안 헤매는 문제.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

package bj;   import java.awt.Point; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer;   public class p1967 {     static ArrayList<Point>[] arrList;     static boolean visit[];     static Point maxP;     static int max=0;     public static void main(String[] args) throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                  int n = Integer.parseInt(br.readLine());         StringTokenizer st;         arrList = new ArrayList[n+1];         visit = new boolean[n+1];         for(int i=0; i<n+1; i++) {             arrList[i] = new ArrayList<>();         }         for(int i=1; i<n; i++) {             st = new StringTokenizer(br.readLine());             int a = Integer.parseInt(st.nextToken());             int b = Integer.parseInt(st.nextToken());             int val = Integer.parseInt(st.nextToken());             arrList[a].add(new Point(b,val));             arrList[b].add(new Point(a,val));         }                  Point tmp = dfs(arrList[1].get(0), 0);         max = 0;         maxP = null;         visit = new boolean[n+1];                  dfs(tmp, 0);         System.out.println(max);     }          public static Point dfs(Point p, int val) {         visit[p.x] = true;                  for(Point tmp : arrList[p.x])             if(!visit[tmp.x])                 dfs(tmp, val+tmp.y);                  if(max < val) {             max = val;             maxP = p;         }                  return maxP;     } }   Colored by Color Scripter

cs