백준 : 1967

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

1967번: 트리의 지름

 

나는 이문제를 모든 정점에 대해서 뿌리 노드들을 구하였다. 그러다보니 메모리초과가 발생하여 자료구조를 많이 바꿔서 pass했다. 다른사람들은 어떻게 풀었는지 궁금해서 검색해보았더니 그리디로 접근 가능한것.

 

1. 임의 정점 a에서 가장 가중치가 큰 노드를 찾는다. b 라고  하겠다.

2. 이제 b에서 가장 가중치가 큰 노드 c를 찾는다.

정답은 b-c 거리가 되겠다. 이게 왜그럴까 생각해보니?? 당연히 되겠거니 생각한다.

 

아래는 내가 복잡하게 푼 소스

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class B1967 {
    static int N;
    static int parent[];
 
    static class Pair {
        int u;
        int w;
 
        public Pair(int u, int w) {
            super();
            this.u = u;
            this.w = w;
        }
 
    }
 
    static class BT {
        int u;
        ArrayList<Pair> list;
 
        public BT(int u) {
            this.u = u;
            list = new ArrayList<>();
 
        }
 
    }
 
    static BT node[];
 
    static int Find(int x) {
        if (x == parent[x]) {
            return x;
        }
        return Find(parent[x]);
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        node = new BT[N + 1];
        parent = new int[N + 1];
        for (int n = 1; n <= N; n++) {
            parent[n] = n;
            node[n] = new BT(n);
        }
 
        for (int n = 1; n < N; n++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            parent[v] = u;
            node[u].list.add(new Pair(v, w));
 
        }
 
        int Answer = 0;
        int root = Find(1);
        // 여기서 구한 두쌍의 합이 가장큰게 정답이다.
        // 정렬 해서 0 1 뽑으면된다.
        for (int n = 1; n <= N; n++) {
            int vSize = node[n].list.size();
            int value[] = new int[vSize];
 
            if (vSize <= 1 && n!=root)
                continue;
            for (int v = 0; v < vSize; v++) {
                value[v] = 0;
                Queue<Pair> q = new LinkedList<>();
                q.add(new Pair(node[n].list.get(v).u, node[n].list.get(v).w));
 
                while (!q.isEmpty()) {
                    Pair tmp = q.poll();
                    value[v] = Math.max(value[v], tmp.w);
 
                    for (int i = 0; i < node[tmp.u].list.size(); i++) {
                        int next = node[tmp.u].list.get(i).u;
                        int sum = node[tmp.u].list.get(i).w + tmp.w;
 
                        q.add(new Pair(next, sum));
                    }
 
                }
 
            }
 
            int sum = 0;
            if (value.length >= 2) {
                Arrays.sort(value);
                sum = value[value.length - 1] + value[value.length - 2];
            } else if (value.length == 1) {
                sum = value[0];
            }
            Answer = Math.max(Answer, sum);
        }
 
        System.out.println(Answer);
 
    }
}