[BOJ 1967] 트리의 지름 (Java)

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

1967번: 트리의 지름

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

public class Main_BOJ_1967 {
	static class Edge{
		int no;
		int weight;
		public Edge(int no, int weight) {
			this.no = no;
			this.weight = weight;
		}
	}
	static ArrayList<ArrayList<Edge>> adjList;
	static int N;
	static boolean[] check;
	static int answer=0;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=null;
		N=Integer.parseInt(br.readLine());
		adjList=new ArrayList<>(N+1);
		for (int i=0; i<=N; i++) {
			adjList.add(new ArrayList<Edge>());
		}
		int a, b, c;
		for (int i=0; i<N-1; i++) {
			st=new StringTokenizer(br.readLine());
			a=Integer.parseInt(st.nextToken());
			b=Integer.parseInt(st.nextToken());
			c=Integer.parseInt(st.nextToken());
			adjList.get(a).add(new Edge(b,c));
			adjList.get(b).add(new Edge(a,c));
		}
		for (int i=1; i<=N; i++) {
			check=new boolean[N+1];
			dfs(i, 0);
		}
		System.out.println(answer);
	}
	private static void dfs(int num, int cnt) {
		check[num]=true;
		if (cnt>answer) answer=cnt;
		for (int i=0; i<adjList.get(num).size(); i++) {
			Edge neighbor=adjList.get(num).get(i);
			if (!check[neighbor.no]) {
				dfs(neighbor.no, cnt+neighbor.weight);
			}
		}
		
	}

}

완전 탐색식으로 풀었다.

1~N번 정점까지 dfs를 돌려 각각 임의의 두 정점 사이의 길이를 구해준다. 그래도 O(N*2) 고, 시간 제한이 2초이므로 가능했지만.. 더 효율적인 풀이가 있었다.

 

결론적으로 말해서 dfs를 2번만 돌리면 된다.

 

임의의 정점에서 dfs를 돌렸을 때 최장 거리가 나오는 점은 무조건 지름을 이루는 두 정점 중 하나일 것이다. (이 아이디어를 떠올리는게 어려웠다)

최장 거리가 나오는 점에 대해 dfs를 또 돌려줘서 최장거리가 나오는 경로가 답이 된다.(지름을 이루는 두 정점은 서로에 대해서 최장 거리일 것이므로)

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

public class Main_BOJ_1967 {
	static class Edge{
		int no;
		int weight;
		public Edge(int no, int weight) {
			this.no = no;
			this.weight = weight;
		}
	}
	static ArrayList<ArrayList<Edge>> adjList;
	static int N;
	static boolean[] check;
	static int answer=0;
	static int longest;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=null;
		N=Integer.parseInt(br.readLine());
		adjList=new ArrayList<>(N+1);
		for (int i=0; i<=N; i++) {
			adjList.add(new ArrayList<Edge>());
		}
		int a, b, c;
		for (int i=0; i<N-1; i++) {
			st=new StringTokenizer(br.readLine());
			a=Integer.parseInt(st.nextToken());
			b=Integer.parseInt(st.nextToken());
			c=Integer.parseInt(st.nextToken());
			adjList.get(a).add(new Edge(b,c));
			adjList.get(b).add(new Edge(a,c));
		}
		check=new boolean[N+1];
		dfs(1,0);
		check=new boolean[N+1];
		answer=0;
		dfs(longest,0);
		System.out.println(answer);
	}
	private static void dfs(int num, int cnt) {
		check[num]=true;
		if (cnt>answer) {
			answer=cnt;
			longest=num;
		}
		for (int i=0; i<adjList.get(num).size(); i++) {
			Edge neighbor=adjList.get(num).get(i);
			if (!check[neighbor.no]) {
				dfs(neighbor.no, cnt+neighbor.weight);
			}
		}
		
	}

}

시간이 무려 2000ms 에서 200ms 로 줄었다.