[백준(Baekjoon)][자바(java)] 1967 : 트리의 지름 / 트리

 

www.acmicpc.net/problem/1967

1967번: 트리의 지름

 

문제 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	
	public static class Node {
		int v, d;
		public Node( int v, int d ) {
			this.v = v;
			this.d = d;
		}
	}
	
	public static class Distance {
		int u, d_sum;
		public Distance( int u, int d_sum ) {
			this.u = u;
			this.d_sum = d_sum;
		}
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		int n = Integer.parseInt( br.readLine() ), v1, v2, w, i, u, v, d;  // vertex1, vertex2, weight, u, v, d
		List<List<Node>> e = new ArrayList<>();  // edge
		for( i = 0; i < n; i++ )
			e.add( new ArrayList<>() );
		StringTokenizer st;
		for( i = 0; i < n-1; i++ ) {
			st = new StringTokenizer( br.readLine() );
			v1 = Integer.parseInt( st.nextToken() ) - 1;
			v2 = Integer.parseInt( st.nextToken() ) - 1;
			w = Integer.parseInt( st.nextToken() );
			e.get( v1 ).add( new Node( v2, w ) );
			e.get( v2 ).add( new Node( v1, w ) );
		}
		br.close();
		
		int d_sum, d_max = 0, s = 0;  // start( root ) node 
		boolean vis[];
		Deque<Distance> q;
		for( i = 0; i < 2; i++ ) {
			vis = new boolean[n];
			q = new ArrayDeque<>();
			d_sum = 0;
			vis[s] = true;
			q.add( new Distance( s, 0 ) );
			while( !q.isEmpty() ) {
				Distance dis = q.remove();
				u = dis.u; d_sum = dis.d_sum;
				if( d_max < d_sum ) {
					d_max = d_sum;
					s = u;
				}
				for( Node nd : e.get( u ) ) {
					v = nd.v; d = nd.d;
					if( !vis[v] ) {
						vis[v] = true;
						q.add( new Distance( v, d + d_sum ) );
					}
				}
			}
		}

		System.out.println( d_max );	
        
	}
}

 

*  BFS

-  Node( 연결된 정점 번호, 거리 ), Distance( 정점 번호, 거리 합 ) 클래스 작성
-  인접 리스트
-  노드 번호 입력 시 1씩 뺌  ( 루트 노드 번호는 0 )
-  트리는 무방향 그래프이므로 간선(edge) 연결 시 v1->v2, v2->v1 양방향으로 연결
-  BFS를 두 번 실행  ( 이전 문제( 1167 : 트리의 지름 hyunjiishailey.tistory.com/276  )와 마찬가지 ) 
  1)  첫 번째에는 시작 정점이 0
  2)  두 번째에는 시작 정점이 이전에 0에서 젤 먼 거리였던 끝 정점
-  큐로 트리를 탐색하면서 간선으로 연결된 거리의 합을 구해가며 가장 먼 거리(d_max)를 갱신