[BOJ] 1167.트리의 지름(그래프, DFS).java

#. Problem

https://www.acmicpc.net/problem/1167

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

안타깝게도 1번 정점이 무조건 Root 라는 보장이 없다.

그래서 나는 무조건 1번 정점에서 가장 먼~ 곳에 있는 정점으로 먼저 이동할 것이다.

이동한다기보다는 가장 먼~ 곳에 있는 정점의 번호와 거리를 저장해두고,

그 정점부터 다시 출발해서 가장 먼~ 곳에 있는 정점을 찾으러 갈 것이다.

#. Code

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

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer;   public class BOJ1167 {       static int V, res, leaf;     static ArrayList<info> relation[];       static class info {         int to;         int wgt;           public info(int to, int wgt) {             this.to = to;             this.wgt = wgt;         }     }       public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;           V = Integer.parseInt(br.readLine()); // 정점 개수         relation = new ArrayList[V+1];         for (int i = 1; i <= V; i++)             relation[i] = new ArrayList<>();         // 연결된 간선의 정보 저장         for (int i = 1; i <= V; i++) {             st = new StringTokenizer(br.readLine(), " ");             int from = Integer.parseInt(st.nextToken());             while (true) {                 int to = Integer.parseInt(st.nextToken());                 if (to == -1)                     break;                 int weight = Integer.parseInt(st.nextToken());                 relation[from].add(new info(to, weight));             }         }           // 특정 정점에서 가장 멀리 있는 노드의 지름과 정보 얻기         dfs(1, 0, 0);         // 리프 노드에서 올라오면서 가장 긴 지름 찾기         dfs(leaf, 0, 0);         System.out.println(res);     }       public static void dfs(int node, int prnt, int wgt) {         if (wgt > res) {             res = wgt;             leaf = node;         }         for (int i = 0; i < relation[node].size(); i++) {             info next = relation[node].get(i);             // 부모 노드는 pass             if (next.to == prnt) continue;             dfs(next.to, node, next.wgt + wgt);         }     } }   Colored by Color Scripter

cs

line 39) 해당 정점과 연결된 정점까지의 거리를 ArrayList에 저장

line 44) 특정(1번) 정점에서 가장 멀리 있는 노드와 그 거리 정보 얻기

line 46) line 44 에서 구한 노드부터 다시 가장 긴 거리를 갖는 노드를 찾으러 gogo

line 50~61) 이 부분이 핵심!

line 51) 현재 노드까지의 거리가 지금까지 구한 최대 거리보다 크다면

line 52~53) 그 거리와 해당 노드를 저장

line 55) 현재 노드와 연결된 노드들을 방문할 것인데

line 58) 내 부모 노드로 다시 돌아가지 못 하도록 pass

line 59) (현재 노드와 연결된 다음 노드, 현재 노드, 지금까지의 거리 + 다음 노드까지의 거리) 를 dfs로 넘겨준다