[BOJ] 백준 [19581] 두 번째 트리의 지름 JAVA

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

19581번: 두 번째 트리의 지름

문제

풀이

트리의 지름을 구하기위해 다음과 같은 방법을 이용해서 구할 수 있었다.

1. 아무노드(1)에서 탐색을하여 제일 먼 것(a)을 선택.

2. 선택한 제일 먼 노드(a)에서 제일 먼 노드를 선택(b)

 a<->b 의 거리가 트리의 지름이다.

 

그러나 , 이 문제에서는 조건이 하나 더 추가된다.

두번째 큰 지름을 구하는것. 위의 1,2번 까지는 똑같이 하면된다.

3. a에서 출발하여 b를 제외한 제일 먼 노드를 선택(c)

4. b에서 출발하여 a를 제외한 제일 먼 노드를 선택(d)

a<->c 와 b<->d 중 max값이 정답이다.

 

 

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
public class Main{
 
    static int N;
    static boolean[] visit;
    static ArrayList<Node>[] list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        list = new ArrayList[N+1];
 
        for(int i=1;i<=N;i++)
            list[i] = new ArrayList<>();
        for(int i=1;i<N;i++){
            int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            list[input[0]].add(new Node(input[1],input[2]));
            list[input[1]].add(new Node(input[0],input[2]));
        }
        Node node1 = bfs(1, 0);
        Node node2 = bfs(node1.node, 0);
        Node result1 = bfs(node1.node, node2.node);
        Node result2 = bfs(node2.node, node1.node);
        System.out.println(Math.max(result1.weight,result2.weight));
 
    }
    static Node bfs(int start,int exNode){
        LinkedList<Node> q = new LinkedList<>();
        q.add(new Node(start,0));
        Node retNode = new Node(start, 0);
        visit = new boolean[N+1];
        while (!q.isEmpty()){
            Node cur = q.poll();
            visit[cur.node]=true;
 
            if(cur.weight > retNode.weight && cur.node!=exNode)
                retNode = cur;
 
            for (Node next : list[cur.node]) {
                if(!visit[next.node] && next.node!=exNode)
                    q.add(new Node(next.node,cur.weight+next.weight));
            }
        }
        return retNode;
    }
    static class Node{
        int node;
        int weight;
 
        public Node(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }
}