[백준] 1167번 - 트리의 지름 (java)

Baekjoon 1167 - 트리의 지름

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	21123	7665	5511	34.599%

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다..

출력

첫째 줄에 트리의 지름을 출력한다.

풀이

1. 하나의 정점을 기준으로 최장거리의 정점을 찾는다.
2. 그 정점으로부터 가장 먼 거리에 있는 정점간 거리가 그래프에서의 최장거리이다.

과정

1.우선순위 큐를 이용하기 위해 Node클래스를 정의한다.

static class Node implements Comparable<Node> {
        int vertex;
        int weight;
        int totalCost;
        Node link;

        public Node(int vertex, int weight, Node link) {
            super();
            this.vertex = vertex;
            this.weight = weight;
            this.link = link;
        }

        public Node(int vertex, int totalCost) {
            super();
            this.vertex = vertex;
            this.totalCost = totalCost;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.weight, o.weight);
        };

2. 최장 거리를 이용하기 위해 Dijkstra를 정의한다.

static void dijkstra(int start) {
        int[] dist = new int[V+1];
        boolean[] visited = new boolean[V+1];

        // Node클래스에서는 Weight가 작은 정점이 우선순위가 높으므로 역으로 설정
        PriorityQueue<Node> pq = new PriorityQueue<>(Collections.reverseOrder());

        pq.offer(new Node(start,0));
        visited[start] = true;

        while(!pq.isEmpty()) {
            Node maxDistNode = pq.poll();

            for(Node temp = adjArray[maxDistNode.vertex]; temp != null ; temp = temp.link) {
                if(!visited[temp.vertex] && dist[temp.vertex] <dist[maxDistNode.vertex] + temp.weight) {
                    dist[temp.vertex] = dist[maxDistNode.vertex] + temp.weight;
                    pq.offer(new Node(temp.vertex,dist[temp.vertex]));
                    visited[temp.vertex] = true;
                }
            }
        }
        for (int i = 1; i <= V ; i++) {
            if(answer< dist[i]) {
                answer = dist[i];
                second = i;// 거리가 가장 먼 정점을 저장한다.
            }

        }
    }

3. 가장 먼 정점이 처음 수행한 임의의 정점과 같지 않다면 한번 더 최장거리를 찾고 출력한다.

최종 소스코드

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

public class BJ_G5_1167 {
    static int V;
    static StringTokenizer st;
    static Node[] adjArray;
    static int answer=0, second = 0;

    static class Node implements Comparable<Node> {
        int vertex;
        int weight;
        int totalCost;
        Node link;

        public Node(int vertex, int weight, Node link) {
            super();
            this.vertex = vertex;
            this.weight = weight;
            this.link = link;
        }

        public Node(int vertex, int totalCost) {
            super();
            this.vertex = vertex;
            this.totalCost = totalCost;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.weight, o.weight);
        };
    }

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

        V = Integer.parseInt(br.readLine());
        adjArray = new Node[V + 1];
        for (int i = 1; i <= V; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            while (true) {
                int end = Integer.parseInt(st.nextToken());
                if (end == -1)
                    break;
                int weight = Integer.parseInt(st.nextToken());
                adjArray[start] = new Node(end,weight,adjArray[start]);
            }
        }

        dijkstra(1);
        if (second != 1)
            dijkstra(second);

        System.out.println(answer);
    }

    static void dijkstra(int start) {
        int[] dist = new int[V+1];
        boolean[] visited = new boolean[V+1];
        PriorityQueue<Node> pq = new PriorityQueue<>(Collections.reverseOrder());

        pq.offer(new Node(start,0));
        visited[start] = true;

        while(!pq.isEmpty()) {
            Node maxDistNode = pq.poll();

            for(Node temp = adjArray[maxDistNode.vertex]; temp != null ; temp = temp.link) {
                if(!visited[temp.vertex] && dist[temp.vertex] <dist[maxDistNode.vertex] + temp.weight) {
                    dist[temp.vertex] = dist[maxDistNode.vertex] + temp.weight;
                    pq.offer(new Node(temp.vertex,dist[temp.vertex]));
                    visited[temp.vertex] = true;
                }
            }
        }
        for (int i = 1; i <= V ; i++) {
            if(answer< dist[i]) {
                answer = dist[i];
                second = i;
            }                
        }
    }
}