[백준BOJ] 1967번 트리의 지름.java

 

백준 저지에서 트리의 지름을 자바를 통해 풀어 보았다. 

 

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

1967번: 트리의 지름

 

1967번 트리의 지름.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

 

1967번 트리의 지름

문제

트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.

이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.
입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다.

트리의 노드는 1부터 n까지 번호가 매겨져있다.

설명

가중치를 가진 트리가 있을 때 가중치를 기준으로 가장 멀리 있는 두 노드 사이의 가중치 합을 구해야 한다. 

 

아무 노드를 선택하고 해당 노드에서 가장 멀리 있는 노드(A)를 선택한다. 다음 해당 노드(A)에서 가장 멀리 있는 노드(B)를 구한다. A노드와 B노드 사이 거리가 문제의 정답이다. 

 

처음에 선택하는 노드는 어떤 노드를 선택해도 상관없기 때문에 1번 노드를 선택한다. BFS를 통해 1번 노드에서 가장 멀리 있는 노드(A)를 구한다. 다음 A노드에서 시작하여 가장 멀리 있는 노드(B)를 구한다. 이 때 A노드에서 B노드까지의 가중치 합이 정답이다.

코드

//1967번 트리의 지름.java
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.Queue;
import java.util.StringTokenizer;

public class 트리의_지름_1967 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws NumberFormatException, IOException {
		int n = Integer.parseInt(br.readLine());
		ArrayList<ArrayList<edge>> graph = new ArrayList();
		for(int i=0;i<=n;i++) {
			graph.add(new ArrayList<edge>());
		}
		for(int i=0;i<n-1;i++) {
			st = new StringTokenizer(br.readLine()," ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());
			graph.get(from).add(new edge(to, value));
			graph.get(to).add(new edge(from, value));
		}
		int[] visit = new int[n+1];
		Arrays.fill(visit, -1);
		visit = bfs(visit, graph, 1);
		
		int max=0;
		int maxIndex=0;
		for(int i=0;i<=n;i++) {
			if(max < visit[i]) {
				max = visit[i];
				maxIndex = i;
			}
		}
		
		Arrays.fill(visit, -1);
		visit = bfs(visit, graph, maxIndex);
		for(int i=0;i<=n;i++) {
			if(max < visit[i]) {
				max = visit[i];
				maxIndex = i;
			}
		}
		System.out.println(max);
	}
    static int[] bfs(int[] visit, ArrayList<ArrayList<edge>> graph, int start) {
    	Queue<Integer> q = new LinkedList<Integer>();
    	visit[start]=0;
    	q.add(start);
    	
    	while(!q.isEmpty()) {
    		int now = q.poll();
    		for(int i=0;i<graph.get(now).size();i++) {
    			edge next = graph.get(now).get(i);
    			if(visit[next.to]==-1) {
    				visit[next.to] = visit[now]+next.value;
    				q.add(next.to);
    			}
    		}
    	}
    	return visit;
    }
    
    static class edge{
    	int to;
    	int value;
    	edge(int to, int value){
    		this.to=to;
    		this.value=value;
    	}
    }
}