백준 |1167번. 트리의 지름 - BFS 응용 문제

⬛ 백준 1167번. 트리의 지름

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

1167번: 트리의 지름

문제

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

입력

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

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

출력

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

---

💚나의 풀이

이 문제는 어쨋든 트리의 지름의 정의가 “가장 긴 경로의 길이” 이므로. 그것을 구하면 된다.

1. 처음에는 시작점을 1로 두고 BFS를 순회하며 distance 배열의 거리를 업데이트한다.
2. distance의 배열 값들 중 max 값이 정점에 대하여 BFS를 다시 시도한다.
3. distance 정렬 후 max인 끝 값이 가장 긴 트리의 지름이 된다.

package to_0830_4;

import java.util.*;
import java.util.Scanner;

/*1167번. 트리의 지름 - BFS 로 풀긴 할거지만 응용*/
class Edge{
	int e;
	int val;
	Edge(int e, int val){
		this.e = e;
		this.val= val;
	}
}
public class Main {
	static int V;
	static int[] distance;//거리
	static boolean[] visited;
	static ArrayList<ArrayList<Edge>> graph;
	//BFS
	static void BFS(int v) {
		Queue<Integer> Q= new LinkedList<>();
		Q.offer(v);
		visited[v] = true;
		
		while(!Q.isEmpty()) {
			int cur = Q.poll();
			for(Edge nx : graph.get(cur)) {
				int nx_e= nx.e;
				int nx_val = nx.val;
				
				if(!visited[nx_e]) {
					visited[nx_e]= true;
					Q.offer(nx_e);
					distance[nx_e] = distance[cur] + nx_val;//직전값+val
				}
			}
		}
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		V = kb.nextInt();//정점 개수
		
		distance = new int[V+1];
		visited = new boolean[V+1];
		
		graph = new ArrayList<>();
		for(int i=0; i<=V; i++) graph.add(new ArrayList<>());
		
		//데이터 입력받을 건데 
		for(int i=1; i<=V; i++) {
			int s = kb.nextInt();//시작 정점 
			while(true) {
				int e= kb.nextInt();
				if(e == -1) break;
				int val = kb.nextInt();
				//양방향인데
				graph.get(s).add(new Edge(e, val));
		
			}
		}
		
		//시작점은 최초에 1로 철 
		BFS(1);
		
		//이제 1 뒤에 가장 max 값 갖는 애부터 시작점 설정하여 BFS 
		int max = 1;
		for(int i=2; i<=V; i++) {
			if(distance[max] < distance[i]) max = i;
		}
		
		distance = new int[V+1];
		visited = new boolean[V+1];
		
		BFS(max); //max값 갖던 애로 다시 BFS 순회하고 나서 나온 값중 
		
		Arrays.sort(distance);//정렬 후 
		System.out.println(distance[V]); //가장 최댓값 출력
	}
}