[ Baekjoon ][JAVA][7812] 중앙 트리

www.acmicpc.net/problem/7812

7812번: 중앙 트리

문제

트리는 사이클을 갖지 않는 연결된 그래프이다.

중앙 정점은 모든 정점으로 이르는 비용의 합이 가장 작은 정점이다. 트리의 정점 개수가 작은 경우에는 모든 경우의 수를 다 계산해보는 프로그램을 이용해 쉽게 구할 수 있다.

위의 그림은 가중치가 있는 트리로, 정점의 개수는 5개이다. 이 트리의 중앙 정점은 B이다.

B-A = 2, B-D = 7, B-C = 1, B-E = 7+5=12, 총: 2+1+7+12 = 22

N이 큰 경우에 문제를 풀어보자.

트리를 입력 받아, 모든 정점과 중앙 정점까지 비용의 합을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄에는 세 정수 a, b, w가 주어진다. (1 ≤ w ≤ 100) a와 b는 간선을 나타내고, w는 그 간선의 가중치이다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스마다 모든 정점과 중앙 정점 사이의 비용의 합을 출력한다.

예제 입력

5
0 1 2
1 2 1
1 3 7
3 4 5
6
0 1 1
1 2 4
2 3 1
3 4 4
4 5 1
0

예제 출력

22
21

접근

기본적인 이진트리와 원리는 같다. down - top 방식으로 각 노드의 자식 노드의 수와 그 cost 값을 전처리해둔 뒤 top - down 방식으로 한 번에 모든 노드의 계산을 끝내는 방식이다.

myFamily[i] 는 "i" 번째 노드를 루트로 생각할 때 갈 수 있는 자식 노드들의 길이 합이며 stranger[i]는 그에 정 반대되는 성질을 갖는, 갈 수 없는 노드들의 길이 합이다.

물론 무방향의 그래프이므로 임의의 노드를 루트로 가정하고 dfs 하는 것이 요리돌리고 죠리돌리면 대체 무슨 의미가 있는가 싶은 분도 있겠지만 이를 논리적으로 극복하기 위해 dfs1() 에서는 0번째 노드를 루트로 생각하고 함수를 시작하며 각각 재귀적으로 파고 들어가는 트리의 모양 그대로 "서있는 것" 처럼 탐색이 가능하다

무방향이긴 하지만 Cycle이 없음이 보장되는 트리형 자료구조이므로 별도의 visit[] 배열 없이 직전 노드(dad)가 무엇인지만 잘 판단하면 탐색이 편하게 진행된다는 점도 특징이다

코드

package baekjoon;
import java.io.*;
import java.util.*;
public class Main {
    private static class Node {
        int next, cost;
        Node(int next, int value){
            this.next = next;
            this.cost = value;
        }
    }
    static int N;
    static long[] size, myFamily, stranger;
    static ArrayList<Node>[] tree;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        while((N = stoi(br.readLine())) != 0){
            init();
            for(int i=1; i<N; i++){
                st = new StringTokenizer(br.readLine());
                int a = stoi(st.nextToken());
                int b = stoi(st.nextToken());
                int cost = stoi(st.nextToken());
                tree[a].add(new Node(b, cost));
                tree[b].add(new Node(a, cost));
            }
            dfs1(0, -1);
            dfs2(0, -1);
            sb.append(findResult() + "\n");
        }
        System.out.println(sb.toString());
    }
    private static void dfs1(int here, int dad) {
        for(Node n : tree[here]){
            if(n.next != dad) {
            	dfs1(n.next, here);
                size[here] += size[n.next];
                myFamily[here] += myFamily[n.next] + size[n.next] * n.cost;
            }
        }
        size[here]++;	// size counting의 핵심
    }
    private static void dfs2(int here, int dad){
        for(Node n : tree[here]) {
            if(n.next != dad) {
                stranger[n.next] += stranger[here] + (size[0]-size[n.next]) * n.cost + myFamily[here] - (myFamily[n.next] + size[n.next] * n.cost);
                dfs2(n.next, here);
            }
        }
    }
    
    private static long findResult(){
        long min = Long.MAX_VALUE;
        for(int i=0; i<N; i++){
            min = Math.min(min, myFamily[i] + stranger[i]);
        }
        return min;
    }
    private static void init(){
        size = new long[N];
        myFamily = new long[N];
        stranger = new long[N];
        tree = new ArrayList[N];
        for(int i=0; i<N; i++){
            tree[i] = new ArrayList<>();
        }
    }
    private static int stoi(String input){
        return Integer.parseInt(input);
    }
   
}