[백준]1967번 트리의 지름

• 트리는 { 사이클 없는 무방향 } 그래프다. → 따라서 node가 N개라면, edge는 N-1개
• Tree에서는 어떤 두 노드를 선택해도, 둘 사이 경로가 항상 하나만 존재한다.
  • Tree에서 { 어떤 두 노드를 선택해 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우 } → Tree의 모든 노드들은 이 두 노드를 "지름의 끝 점으로 하는 원 " 안에 들어가게 된다.
  • 이런 두 노드 사이의 경로 —> 트리의 지름.
  • 즉, { 트리에 존재하는 모든 경로 중 가장 긴 것 } 의 길이 → 트리의 지름
• 노드의 개수는 1만이하

풀이 생각

• 💥💥 1167 번 트리의 지름은 풀었었는데 💥💥 이 문제를 30분동안 풀지 못하고 있다.
• 트리의 구조상 , 지름을 이루는 두 노드는 leaf node일 것이다.
  • leaf node는 parent node만을 가질 것이다. → 따라서 인접한 노드의 개수가 1개
• 가장 먼저 드는 생각은 완전탐색
  • 탐색을 이용하여, 두 노드 사이의 거리를 모두 구해보기 .
  • 그런데 이렇게 할 경우, DFS를 사용하더라도 O(V+E) 인데
  • 이러한 DFS를, 최대 5000번 을 하게 된다면 5000 x (10000+9999) → 몇 억이 나오게 된다.
• 완전탐색이 아니게 풀어 볼 수 있는 방법???
  1. leaf노드들에 대해서만 실행한다.
  • 중복되는 경로가 많을 것을 생각하면 DP를 이용할 수 있을까? —> 여기서는 생각하기가 좀 어려운 것 같다.
    • 기존에 내가 자주사용하던 방식은, 적어도 cur ~ end까지를 cache하거나 start~ cur까지를 cache하는 방식이었다.
    • 그래도 결국은 10000 x 10000 가지의 경우에 대해 dfs를 실행하게 되기 때문에 이 방법은 적절하지 않은 문제였다.

다른 사람 풀이

• 지난번에 1167번 트리의지름 문제를 풀었었음에도 이 문제를 또 다시 풀지 못했다.
• 생각해보니 (시작점,끝점) 조합을 반드시 만들어서 굳이 dfs를 할 필요가 없다...
• 임의의 점(a)에서, 모든 점을 방문할 때 까지만 dfs를 한다. —> 임의의 점에서 최대 길이가 되는 노드(b)를 찾는다. —> a가 intermediary node더라도, b는 leaf node일 거임.
  • a가 leaf이던, intermediary node이던 , a에서 가장 멀리 떨어진 노드는 intermediary node일 수가 없음. 당연히 intermediary node에 연결된 leaf 노드가 더 멀리 떨어져있는 것일테니.
• 해당 노드(b)를 시작점으로 해서, 다시 dfs를 해서 가장 긴 길이를 갖게 되는 노드 (c)를 찾는다. —> b-c가 트리의 지름이 된다.

package coding;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int max=0;
    public static int maxNode=0;
    public static int n;
    public static List<int[]>[] graph= new ArrayList[10000];
    public static boolean[] visit = new boolean[10000]; // 매 번 초기화
    public static void Setting() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        // graph(tree) setting
        for(int i=0;i<n;i++)
            graph[i]= new ArrayList<>();
        int p=0,c=0,w=0;
        for(int i=0;i<n-1;i++){
            st = new StringTokenizer(br.readLine());
            p = Integer.parseInt(st.nextToken())-1;
            c = Integer.parseInt(st.nextToken())-1;
            w = Integer.parseInt(st.nextToken());
            graph[p].add(new int[]{c,w});
            graph[c].add(new int[]{p,w});
        }
    }
    public static void dfs(int cur,int cost){
        // leaf node에 도달시 cost를 check하고 , 0번으로무터 max값의 cost를 갖는 node를 maxNode로 저장
        if(graph[cur].size()==1) {
            if(cost>max){
                max=cost;
                maxNode = cur;
            }
            // 여기 return을 하면 안 된다 
            // 만약 첫 번째 노드가 leaf node였다면 그대로 종료가 되버림 
            // 어차피 인접한 노드가 이미 모두 방문한 노드라면 아래 로직도 빠르게 통과 
        }
        int[] next =null;
        // 인접 노드에 방문하기
        for(int i=0;i<graph[cur].size();i++){
            next =graph[cur].get(i);
            // 이미 방문한 노드는 pass
            if(visit[next[0]]) continue;
            // 다음 노드를 방문한다.
            visit[next[0]]=true;
            dfs(next[0],cost+next[1]);
        }
    }
    public static void solve() {
				// 0번 노드에서 시작 -> 모든 노드를 방문 -> 최대 길이의 path를 갖는 노드를 maxNode로 update
        visit[0] = true;
        dfs(0, 0);
        // visit을 초기화하고 maxNode로부터, 모든 노드를 방문 ->최대 길이의 path의 길이를 max로 update 
        Arrays.fill(visit, false);
        visit[maxNode] = true;
        max = 0;
        dfs(maxNode, 0);

    }
    public static void main(String[] args) throws IOException {
        Setting();
        solve();
        System.out.println(max);
    }
}