Print
카테고리: [ Algorithm ]
조회수: 3109

트리는 사이클이 없는 비선형 그래프로 임의의 노드를 루트로 잡았을 때 계속 트리가 된다는 특징이 있다.

1. 임의의 시작 노드를 정하고 해당 노드로부터 가장 멀리 떨어진 노드를 찾는다.

2. 가장 멀리 떨어진 노드를 루트 노드로 만든다.

3. 루트 노드에서 가장 멀리 떨어진 노드까지의 길이가 트리의 지름이 된다.

즉, BFS 2번을 사용하여 해당 문제를 해결할 수 있다.


주의할 점

  1. 메모리 초과 주의
  2. 양방향

참고 : https://koosaga.com/14

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static LinkedList[] tree;
    public static boolean[] isVisit;
    public static int[] nodeValue;

    public static int n;
    public static Queue queue;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        tree = new LinkedList[n + 1];
        isVisit = new boolean[n + 1];
        nodeValue = new int[n + 1];

        for (int i = 1; i <= new="" node="">();
        }

        int startNode = 0;
        for (int i = 1; i <= n="" -="" stringtokenizer="" st="new" int="" start="Integer.parseInt(st.nextToken());" destination="Integer.parseInt(st.nextToken());" weight="Integer.parseInt(st.nextToken());" new="" if="" i="" startnode="start;" max="0;" index="0;" for=""> max) {
                max = nodeValue[i];
                index = i;
            }
        }

        for (int i = 1; i <= max="Math.max(max," for="" int="" i="" public="" static="" void="" queue="new" integer="">();

        queue.add(node);

        while (!queue.isEmpty()) {
            int currentNode = queue.poll();
            isVisit[currentNode] = true;

            for (Node nextNode : tree[currentNode]) {
                if (!isVisit[nextNode.node]) {
                    queue.add(nextNode.node);
                    nodeValue[nextNode.node] = nodeValue[currentNode] + nextNode.weight;
                }
            }
        }
    }
}

class Node {
    int node;
    int weight;

    Node(int node, int weight) {
        this.node = node;
        this.weight = weight;
    }
}