1167.백준 트리의 지름 (시간초과...)

1

import java.io.BufferedReader;

2

import java.io.InputStreamReader;

3

import java.util.ArrayList;

4

import java.util.List;

5

import java.util.Scanner;

6

import java.util.StringTokenizer;

7

import java.util.Vector;

8

​

9

class Edge {

10

    int num, dist;

11

​

12

    public Edge(int num, int dist) {

13

        this.num = num;

14

        this.dist = dist;

15

    }

16

}

17

​

18

class Main {

19

​

20

    // 내용: 깊이탐색, 간단한 노드 및 트리 구성법 (as 무향그래프)

21

    // 출처: http://blog.naver.com/occidere/220961873786

22

    static StringTokenizer st;

23

    static int[] visited;

24

    static List<Edge> tree[];

25

26

    static Edge farthestNode;

27

    static int maxDist;

28

    static int farIndex;

29

30

    public static void main(String args[]) throws Exception {

31

​

32

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

33

34

        int DATA_SIZE = Integer.parseInt(br.readLine());

35

        visited = new int[DATA_SIZE + 1];

36

        tree = new ArrayList[DATA_SIZE + 1];

37

        for (int i = 0; i < tree.length; i++) {

38

            tree[i] = new ArrayList<Edge>();

39

        }

40

​

41

        // 한번에 문장을 읽기

42

        String[] infoList = new String[DATA_SIZE];

43

        for (int i = 0; i < DATA_SIZE - 1; i++) {

44

            infoList[i]=br. readLine();

45

        }

46

47

        String[] info;

48

        int parent, index, child, dist;

49

        for (int i = 0; i < DATA_SIZE - 1; i++) {

50

            info = infoList[i].trim().split(" ");

51

            parent = Integer.parseInt(info[0]);

52

            index = 1;

53

            while (index < info.length - 1 ) {

54

                child = Integer.parseInt(info[index++]);

55

                dist = Integer.parseInt(info[index++]);

56

                tree[parent].add(new Edge(child, dist));

57

                tree[child].add(new Edge(parent, dist));

58

            }

59

        }

60

61

        // 다행스럽게 루트를 알려주었다.

62

        maxDist = 0;

63

        dfs(1, 0); // 1. 어느 지점에서 가장 먼 노드를 구하고

64

        maxDist = 0;

65

        dfs(farIndex, 0); // 2. 그 트리에서 가장 먼 거리를 구하면 답이 된다더라...

66

67

        System.out.println(String.valueOf(maxDist));

68

    }

69

​

70

    private static void dfs(int curIndex, int dist) {

71

        visited[curIndex] = 1;

72

​

73

        for (Edge aNode : tree[curIndex]) {

74

            if (visited[aNode.num] != 1) {

75

                dfs(aNode.num, dist + aNode.dist);

76

            }

77

        }

78

​

79

        if (maxDist < dist) {

80

            maxDist = dist;

81

            farIndex = curIndex;

82

        }

83

​

84

        visited[curIndex] = 0;

85

    }

86

​

87

​

88

}