백준 7812 중앙트리 (Java)

문제 URL : https://www.acmicpc.net/problem/7812

 

 

문제 접근법 :모든 노드의  비용의 합을 다구하는 문제입니다.

대표적인 트리 dp 문제인데 

 

증명은 https://www.youtube.com/watch?v=T81Bpx2OmS4

이 유튜브를 참고하는게 좋을것같습니다. 

leetcode 문제인데 이문제와 유사하며 거기에 가중치가 있을 뿐입니다.

 

간단하게 하나의 루트로부터 모든 비용을 구한후 다음 노드에서의 가중치의 합을 구할려면

그 가중치로부터  노드의개수가 n일때 n-child의 개수만큼 비용을 똑같이 더해주고 그리고 -child의 개수만큼 빼줘야하는데

n- child - child 의 공식이 나옵니다.

그래서 가중치를 곱하면 끝입니다.

 

소스코드 : 

import java.io.*;
import java.util.*;

public class Main {
    public static int n;
    public static List<long[]>adj[];
    public static long []val,child;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        while(true) {


            n = sc.nextInt();
            if (n==0)break;

            adj = new ArrayList[n];
            val = new long[n];
            child = new long[n];
            Arrays.fill(child,1);
            for(int i =0;i<n;i++)adj[i]=new ArrayList();
            for(int i =0;i<n-1;i++) {
                int a, b,c;
                a = sc.nextInt();
                b = sc.nextInt();
                c = sc.nextInt();
                adj[a].add(new long[]{b,c});
                adj[b].add(new long[]{a,c});
            }
            val[0]=dfs(0,-1,0);
            dfs2(0,-1);
            System.out.println(Arrays.stream(val).min().orElseThrow());
        }
    }
    public static long dfs(long cur,long parent,long sum){
        long total = sum;
        for(long next[]:adj[(int)cur]) {
            if(next[0]!=parent){
                total+=dfs(next[0],cur,sum+next[1]);
                child[(int)cur]+=child[(int)next[0]];
            }
        }
        return total;
    }
    public static void dfs2(int cur,int parent){
        for(long next[]:adj[cur]) {
            if(next[0]!=parent){
                val[(int)next[0]]=val[cur] + (n-child[(int)next[0]]*2)*next[1];
                dfs2((int)next[0],cur);
            }
        }
    }
}

 

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.