[BOJ][Java] 1167번 트리의 지름

문제 설명

 

문제 링크 : https://www.acmicpc.net/problem/1167

 

트리는 순환하지 않는다는 특징을 가지고 있고

그렇기에 위에 문제에서 하나의 정점에서 다른 하나의 정점까지의 거리는 하나가 나온다.

트리의 임의의 정점을 2개 골랐을 때 그 정점사이의 거리가 가장 긴 경우를 지름이라고 한다.

 

단순히 생각해보면 모든 정점 간의 거리를 구하면 될 것 같지만 정점의 수가 100,000 이기 때문에 

시간초과가 발생한다.

따라서 탐색의 범위를 줄여야 한다.

 

해당 문제를 풀때 아이디어는 임의의 한 정점에서 시작해서 다른 정점까지의 거리를 모두 구한 뒤 그중

가장 멀리있는 정점이 해당 트리의 지름의 한 끝점이라는 것이다.

 

트리의 지름의 한 끝점을 구할 때 BFS를 한번 쓰고, 

해당 끝점에서 BFS를 사용하여 각 정점까지의 거리 중 가장 긴 거리를 찾으면 해당 거리가 

트리의 지름이 된다.

 

각각의 정점 사이의 거리가 있기 때문에 Node 클래스를 선언하여 가중치를 포함하여 선언하고,

나머지는 위의 설명한 로직대로 작성하여 풀었다.

 

package boj;

import java.util.*;
import java.io.*;

public class Main {
    static int V;
    static List<List<Node>> graph = new ArrayList<>();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        V = Integer.parseInt(br.readLine());
        for(int i = 0; i <= V; i++){
            graph.add(new ArrayList<>());
        }

        for(int i = 0; i < V; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());

            while(true){
                int next = Integer.parseInt(st.nextToken());
                if(next == -1) break;
                int d = Integer.parseInt(st.nextToken());

                graph.get(start).add(new Node(next, d));
            }
        }

        int[] checkSum = new int[V+1];
        int[] answerSum = new int[V+1];

        bfs(1,checkSum);
        int maxCheck = 0;
        int maxCheckIdx = 0;

        for(int i = 0; i < checkSum.length; i++){
            if(maxCheck < checkSum[i]){
                maxCheck = checkSum[i];
                maxCheckIdx = i;
            }
        }

        bfs(maxCheckIdx, answerSum);

        System.out.println(Arrays.stream(answerSum).max().getAsInt());

    }

    static void bfs(int s, int[] sum){
        Queue<Node> q = new LinkedList<>();
        boolean[] visited = new boolean[V+1];
        visited[s] = true;
        q.add(new Node(s,0));

        while(!q.isEmpty()){
            Node now = q.poll();

            for(Node node: graph.get(now.end)){
                if(!visited[node.end]){
                    visited[node.end] = true;
                    sum[node.end] = sum[now.end] + node.dis;
                    q.add(node);
                }
            }
        }

    }

    static class Node{
        int end;
        int dis;

        public Node(int end, int dis){
            this.end = end;
            this.dis = dis;
        }
    }

}