[문제 풀이] 백준 1167번 트리의 지름

문제 링크 : https://www.acmicpc.net/problem/1167

 

문제를 풀기 전, 트리의 정의를 먼저 보고 가겠습니다. 

 

https://velog.io/@kjh107704/%ED%8A%B8%EB%A6%AC-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EA%B8%B0%EC%B4%88

[ 트리 ] 트리의 기초

 

간단하게 요약하면, 사이클이 없는 그래프입니다. 

 

풀이

문제에서 구하라는 트리의 지름이 무엇인지에 대해 먼저 보고 가겠습니다. 

 

트리 1

 

트리 1에서 서로 가장 먼 두 노드 간의 거리를 트리의 지름이라고 문제에서 말해주고 있습니다. 만일 모든 간선의 가중치가 1인 경우 가장 먼 노드의 집합은 8과 9이며 그 값은 6입니다. 

 

트리 2

근데 만약 1번 노드와 4번 노드의 가중치가 100이라면 가장 먼 노드의 집합은 8,4 혹은 9,4가 됩니다. 

 

트리3

그럼 이 트리 3에서는 어떨까요. 트리의 지름을 가지는 노드의 집합은 9,7이 됩니다. 

 

즉 모든 노드에서 탐색을 수행한다면 N^3의 시간복잡도가 나오기 때문에 다른 방법을 생각해야 합니다. 

 

트리 4

 

트리를 단순화시켜봤습니다. 위 트리에서 트리의 지름을 구하는 케이스를 생각해 봅시다.

 

우선 트리 1,2와 같이 "sub1의 최대 지름 + sub2의 최대지름 + R에서 sub1의 비용 + R에서 sub2의 비용"이 트리의 지름이 될 수 있습니다. 

 

그럼 트리 3과 같이 R을 지나지 않고 트리의 지름을 이루는 경우는 아래의 트리를 통해 나타낼 수 있습니다. 

트리 5

만일 sub3의 지름 + sub4의 지름이  "sub1의 최대 지름 + sub2의 최대지름 + R에서 sub1의 비용 + R에서 sub2의 비용" 보다 크다면 트리의 지름을 구하는 경로에 R이 포함되지 않습니다. 

 

위 2가지 상황을 정리해 볼 수 있습니다. 

 

1. 트리의 지름은 루트의 서브트리 중 제일 값이 큰 N(>=1) 개의 지름의 합

2. 트리의 지름은 모든 서브트리 중 제일 값이 큰 2개의 지름의 합 

 

이 2가지의 상황에서 항상 포함되는 노드는 루트노드에서 가장 먼 노드라는 것을 생각해 낼 수 있습니다. 

 

즉 루트 노드에서 탐색하여 구한 가장 먼 노드 N1은 트리의 지름을 구하는데 무조건 들리게 되니 N1에서 탐색을 통해 가장 먼 노드와의 거리를 구해주면 됩니다. 

 

+

N1에서 가장 먼 노드의 거리를 구하는 과정에서 DP를 도입해 봤는데, 특정 점을 중복하여 방문하는 경우가 없어서 쓸모가 없습니다ㅠ.

 

시간도 더 오래 걸리더라고요.

 

 

코드

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

public class Num1167트리의지름 {
    private static class Edge{
        int end;
        int cost;
        Edge(int end,int cost){
            this.end = end;
            this.cost = cost;
        }
    }
    static int n,depthNode,maxCost;
    static List<List<Edge>> map;
    static int[] memo;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new ArrayList<>();
        memo = new int[n+1];
        for(int i=0;i<=n;i++){
            map.add(new ArrayList<>());
        }

        // Input
        // can start 1
        Arrays.fill(memo,-1);
        for(int i=0;i<n;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int node = Integer.parseInt(st.nextToken());
            while (true){
                int end = Integer.parseInt(st.nextToken());
                if(end == -1) break;
                int cost = Integer.parseInt(st.nextToken());
                map.get(node).add(new Edge(end,cost));
            }
        }
        maxCost = 0;
        depthNode = 0;
        findMaxDepth(0,1,0);
//        System.out.println(depthNode);
        System.out.println(DFS(0,depthNode));
    }

    public static void findMaxDepth(int preNode,int nowNode,int totalCost){
        for(Edge next : map.get(nowNode)){
            if(next.end == preNode) {
                if(maxCost <totalCost){
                    depthNode = nowNode;
                    maxCost = totalCost;
                }
                continue;
            }
           findMaxDepth(nowNode,next.end,totalCost+next.cost);
        }
    }
    public static int DFS(int preNode ,int nowNode){
        if(memo[nowNode] !=-1) return memo[nowNode];
        memo[nowNode] = 0;
        for(Edge next : map.get(nowNode)){
            if(next.end == preNode) continue;
            memo[nowNode] = Math.max(memo[nowNode],DFS(nowNode,next.end)+next.cost);
        }
        return memo[nowNode];
    }
}