[백준] 1167 트리의 지름 [자바]

 

 

---

https://www.acmicpc.net/board/view/83695

글 읽기 - [힌트] 야매 증명 이지만 직관적으로 이해되는 증명. 저처럼 헤매지 마세요.

https://www.acmicpc.net/board/view/67245

글 읽기 - 4%에서 '틀렸습니다'로 고생하고 있다면..

 

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;
class Point {
	int destination;
	int distance;
	public Point(int des, int dis) {
		this.destination = des;
		this.distance = dis;
	}
}

public class Main {
	static ArrayList<ArrayList<Point>> list = new ArrayList<>();
	static boolean[] visit;
	static int result = 0;
	static int rede = 0;
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		//StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 		int V = Integer.parseInt(br.readLine());
 		visit = new boolean[V+1];
 		for(int i = 0; i <= V; i++) {
 			list.add(new ArrayList<Point>());
 		}
 		for(int i = 0; i < V; i++) {
 			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 			int a = Integer.parseInt(st.nextToken());
 			while(true) {
 				int b = Integer.parseInt(st.nextToken());
 				if(b == -1)
 					break;
 				int c = Integer.parseInt(st.nextToken());
 				list.get(a).add(new Point(b,c));
 			}		
 		}
 		visit[1] = true;
 		dfs(1,0);
 		visit = new boolean[V+1];
 		visit[rede] = true;
 		dfs(rede, 0);
 		System.out.println(result);
 	}
 	static void dfs(int n, int sum) {
 		for(int i = 0; i < list.get(n).size(); i++) {
 			int des = list.get(n).get(i).destination;
 			int dis = list.get(n).get(i).distance;
 			if(!visit[des]) {
 				visit[des] = true;
 				dfs(des, sum+dis);
 			}
 		}
 		if(result < sum) {
 			rede = n;
 			result = sum;
 		}
 	}
}

 

 

---

https://www.acmicpc.net/source/42510900

로그인

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

class Node {
	int v;
	int w;
	Node next;
	Node(int v, int w, Node next) {
		this.v = v;
		this.w = w;
		this.next = next;
	}
}
public class Main {
	static Node[] graph;
	static boolean[] visited;
	static int diameter;
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		//StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 		int V = Integer.parseInt(br.readLine());
 		
 		graph = new Node[V+1];
 		visited = new boolean[V+1];
 		for(int i = 0; i < V; i++) {
 			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 			int a = Integer.parseInt(st.nextToken());
 			while(true) {
 				int b = Integer.parseInt(st.nextToken());
 				if(b == -1)
 					break;
 				int c = Integer.parseInt(st.nextToken());
 				graph[a] = new Node(b,c,graph[a]); //중첩되면 기존의 graph[a]를 새로운 graph[a]의 next로 이동
 			}
 		}
 		dfs(1);
 		System.out.println(diameter);
 	}
 	static int dfs(int n) {
 		visited[n] = true;
 		
 		int a,b,c;
 		a = b = 0;
 		
 		for(Node node = graph[n]; node != null; node = node.next) {
 			if(visited[node.v]) //목적지를 이미 방문했으면
 				continue;
 			c = dfs(node.v) + node.w; //dfs탐색 + 현재 정점끼리의 거리
 			if(a < c) { //현재 탐색했는 거리가 a보다 크면
 				b = a;
 				a = c; //a에 거리를 넣는다
 			}
 			else if(b < c) { //현재 탐색했는 거리가 b보다 크면
 				b = c; //b에 거리를 넣는다
 			}
 			//1에서 시작한 dfs에서 갈래가 여러가지인 경우 여러가지 갈래 중 가장 긴 거리(a)와 두번째로 긴 거리(b)가 정답이 될 것이다
 			//1-2, 1-3-4
 			//정점 1에서 정점 4 가 트리의 지름일 경우 a,b 중 하나는 트리의 지름이고 나머지 하나는 0일 것이다
 			//정점 2에서 정점 4 가 트리의 지름일 경우 a,b 중 하나는 1에서 4까지의 거리이고 나머지 하나는 1에서 2까지의 거리일 것이다
 		}
 		
 		c = a + b; //정점 1에서 가장 긴 거리 + 정점 1에서 두번째로 긴 거리
 		if(diameter < c)
 			diameter = c;
 		return a; //가장 긴 거리의 값을 구한다
 	}
}