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

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

문제

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

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 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.우선순위 큐를 이용하기 위해 Node클래스를 정의한다.

static class Node implements Comparable { 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 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]

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 { 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 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]

from http://skdltm117.tistory.com/28 by ccl(A) rewrite - 2021-09-21 19:01:38