백준 1167번 : 트리의 지름

1. 문제 설명 (1167)

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

2. 분류

• DFS
  
  

3. 풀이

DFS를 활용한 문제이다. 무모하게 dijkstra 알고리즘 을 때려박다가 시간초과를 맞고 조용히 트리의 지름을 구하는 방법을 생각했다. 생각만으로 안나와서, 그냥 구글링을 통해 트리의 지름을 구하는 방법을 찾았다.

다음과 같은 방법을 통해 트리의 지름을 구했다.

1. 임의의 정점 으로부터 가장 먼 정점 A 를 찾는다.
2. 해당 정점 으로부터 가장 먼 정점 B 를 찾는다.
3. A와 B간의 거리 를 구한다.

따라서 간단히 DFS를 두 번 사용하여 풀었다.

정점 1을 임의의 정점으로 두고 DFS를 통해 가장 먼 정점(now)과 그 정점까지의 거리(len)를 구하고, 해당 정점(now)에서 DFS를 통해 가장 먼 정점을 찾고 거리를 갱신했다.

푸는 과정에서 두 가지 실수를 했는데,

1. 28번째 줄 : if(to > i) 의 조건문을 통해 절반짜리 리스트를 구현해버렸고(?),
2. 29번째 줄 : Integer.parseInt(temp[0]) 대신 list[i].add(new Node(to, c)); 를 하다가 틀렸다. (무조건 123… 순서로 나오겠지 하는 안일한 생각)

님들은 실수하지 않으셨길 바랍니다 ㅎㅎ

4. 코드

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 72 73

import java.io.*; import java.util.*;   public class Q1167 {          static int now;     static ArrayList<Node> list[];     static boolean[] visited;     static int max = 0;          public static void main(String args[]) throws Exception{         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         int V = Integer.parseInt(br.readLine());         list = new ArrayList[V+1];         for(int i = 1; i <= V; i++)             list[i] = new ArrayList<>();                  for(int i = 1; i <= V; i++) {             String[] temp = br.readLine().split(" ");                          for(int j = 1; j < temp.length; ) {                 if(Integer.parseInt(temp[j]) == -1)                     break;                                  int to = Integer.parseInt(temp[j]);                 int c = Integer.parseInt(temp[j+1]);                 //if(to > i)                     list[Integer.parseInt(temp[0])].add(new Node(to, c));                 j += 2;             }                      }                  //1번 정점에서 가장 먼 node = now         visited = new boolean[V+1];         dfs(1, 0);         //now에서 가장 먼 node까지의 거리         visited = new boolean[V+1];         dfs(now, 0);         bw.write(max+"");         System.out.println(list[4]);         bw.flush();         bw.close();     }          public static void dfs(int v, int len) {         if (len > max) {             max = len;             now = v;         }           visited[v] = true;           for(Node n : list[v]) {             if(!visited[n.now]) {                 dfs(n.now, n.weight + len);                 visited[n.now] = true;             }         }     }          static class Node {         int now, weight;                  Node(int n, int w) {             this.now = n;             this.weight = w;         }       } }   Colored by Color Scripter

cs

5. 결과

940ms로 잘 작동한다. 1104ms는 LinkedList 로 했을 경우의 결과인데, 딱히 LinkedList 를 쓸 필요는 없다.