#백준_1167 트리의 지름 - Java

유형 : 트리

# 트리에서 탐색은 dfs,bfs가 많이 사용됨.

맨 처음에는 배열로 접근하여 dfs로 문제를 풀었으나, 메모리 초과가 나옴. 대신 인접리스트를 사용하여 문제를 해결하였더니 메모리 제한은 뜨지 않았음. 

 

트리의 지름을 구하는 방법을 알아야 풀 수 있던 문제, 맨 처음에 dfs를 사용하여 가장 긴 길이를 갖고 있는 정점을 구한 후, 그 정점을 기준으로 다시 dfs를 사용하여 트리의 지름을 얻어야함.

 

트리의 지름 구하는법

1. 가장 긴 길이를 갖고있는 정점을 구한다.

2. 가장 긴 길이의 정점을 기준으로 다시 거리를 측정한다.

3. 거리를 저장한 배열 중 최대값이 트리의 지름이다.

 

1) 메모리 초과 났던 코드

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 59 60 61

package bj;   import java.awt.Point; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer;   public class p1167_memoryout {     static int arr[][];     static int n;     static boolean visit[];     static int max=0;     public static void main(String[] args) throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         n = Integer.parseInt(br.readLine());         arr = new int[n+1][n+1];         visit = new boolean[n+1];         StringTokenizer st;         for(int i=0; i<n; i++) {             st = new StringTokenizer(br.readLine());             int index = Integer.parseInt(st.nextToken());             int next = Integer.parseInt(st.nextToken());             int val = Integer.parseInt(st.nextToken());                          arr[index][next] = val;             arr[next][index] = val;                          int tmp = Integer.parseInt(st.nextToken());             while(tmp!=-1) {                 next = tmp;                 val = Integer.parseInt(st.nextToken());                 arr[index][next] = val;                 arr[next][index] = val;                 tmp = Integer.parseInt(st.nextToken());             }                      }         for(int i=1; i<=n; i++) {             dfs(i,0); //            System.out.println();         }         System.out.println(max);     }          public static void dfs(int v, int val) { //        System.out.println(v+" "+val);         visit[v] = true;         max = Math.max(max, val);                  for(int i=1; i<=n; i++) {             if(!visit[i] && arr[v][i]!=0) {                 dfs(i, val+arr[v][i]);                 visit[i] = false;             }         }     } }   Colored by Color Scripter

cs

 

2) 정답 코드

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 59 60 61 62 63 64 65 66 67 68 69 70 71

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.List; import java.util.StringTokenizer;   public class p1167 {     static int n, max = 0;     static Point maxP;     static boolean visit[];     static List<Point>[] arrList;     public static void main(String[] args) throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         n = Integer.parseInt(br.readLine());                  arrList = new ArrayList[n+1];         visit = new boolean[n+1];         StringTokenizer st;                  for(int i=0; i<n+1; i++)             arrList[i] = new ArrayList<>();                  for(int i=0; i<n; i++) {             st = new StringTokenizer(br.readLine());             int index = Integer.parseInt(st.nextToken());             int next = Integer.parseInt(st.nextToken());             int val = Integer.parseInt(st.nextToken());                          arrList[index].add(new Point(next, val));             arrList[next].add(new Point(index, val));                          int tmp = Integer.parseInt(st.nextToken());             while(tmp!=-1) {                 next = tmp;                 val = Integer.parseInt(st.nextToken());                                  arrList[index].add(new Point(next,val));                 arrList[next].add(new Point(index, val));                                  tmp = Integer.parseInt(st.nextToken());             }                      }                  Point tmp = dfs(arrList[1].get(0), 0);         visit = new boolean[n+1];         maxP = null;         max = 0;         dfs(tmp, 0);         System.out.println(max);     }     private static Point dfs(Point p, int val) {         // TODO Auto-generated method stub         visit[p.x] = true;                  for(Point t : arrList[p.x]) {             if(!visit[t.x])                 dfs(t, val+t.y);         }         if(max < val) {             max = val;             maxP = p;         }         return maxP;     } }   Colored by Color Scripter

cs