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

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

1167번: 트리의 지름

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

public class Main_BOJ_1167 {
	static class Edge{
		int node, dist;
		Edge(int node, int dist){
			this.node=node;
			this.dist=dist;
		}
	}
	static int V;
	static ArrayList<ArrayList<Edge>> adjList=new ArrayList<>();
	static int maxVertex;
	static int maxDist;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=null;
		V=Integer.parseInt(br.readLine());
		for (int i = 0; i < V+1; i++) {
			adjList.add(new ArrayList<>());
		}
		for (int i=0; i<V; i++) {
			st=new StringTokenizer(br.readLine());
			int num=Integer.parseInt(st.nextToken());
			while (true) {
				int neighbor=Integer.parseInt(st.nextToken());
				if (neighbor==-1) break;
				int cost=Integer.parseInt(st.nextToken());
				adjList.get(num).add(new Edge(neighbor, cost));
			}
		}
		
		bfs(1, new boolean[V+1]); //최장 거리에 있는 점 리턴
		bfs(maxVertex, new boolean[V+1]); //최장거리에 있는 점에서 최장 거리를 갖는 거리 구함
		System.out.println(maxDist);
	}
	private static void bfs(int num, boolean[] visited) {
		maxVertex=-1;
		maxDist=-1;
		Queue<int[]> q=new LinkedList<>();
		q.add(new int[] {num,0});
		visited[num]=true;
		while (!q.isEmpty()) {
			int[] curr=q.poll();
			int vertex=curr[0];
			int dist=curr[1];
			if (maxDist<dist) {
				maxDist=dist;
				maxVertex=vertex;
			}
			for (int i=0; i<adjList.get(vertex).size(); i++) {
				Edge e=adjList.get(vertex).get(i);
				if (!visited[e.node]) {
					visited[e.node]=true;
					q.add(new int[] {e.node, dist+e.dist});
				}
			}
		}
		//System.out.println(maxVertex+" "+maxDist);
	}

}

아이디어를 잘 잡는게 중요했던 bfs/dfs 두 번 돌리는 문제.

 

트리의 지름을 구하는 방식은 이렇다: 임의의 한 점을 잡아 제일 먼 거리에 있는 어떤 점을 구한다. (지름이므로 트리 속에서 random하게 어떤 vertex를 잡아도 최장 거리가 나오는 점이 지름에 속하는 점이 되게 된다) 그 구한 어떤 점에서 또 한번 BFS/DFS를 돌려 그 점에서 최장 거리를 갖는 점과 그 거리를 구하면 지름이 구해진다.