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

 

www.acmicpc.net/problem/1167

1167번: 트리의 지름

 

문제 풀이

 

import java.util.*;

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 {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), i, u = 0, v = 0, d = 0;
		List<List<Node>> e = new ArrayList<>();
		for( i = 0; i < n; i++ )
			e.add( new ArrayList<>() );
		for( i = 0; i < n; i++ ) {
			u = sc.nextInt() - 1;
			while( true ) {
				v = sc.nextInt() - 1;
				if( v == -2 )
					break;
				d = sc.nextInt();
				e.get( u ).add( new Node( v, d ) );
			}
		}
		sc.close();
		
		int d_sum, d_max = 0, s = 0;
		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 ee : e.get( u ) ) {
					v = ee.v; d = ee.d;
					if( !vis[v] ) {
						vis[v] = true;
						q.add( new Distance( v, d + d_sum ) );
					}
				}
			}
		}

		System.out.println( d_max );
        
	}
}

 

*  BFS

-  Node( 연결된 정점 번호, 거리 ), Distance( 정점 번호, 거리 합 ) 클래스 작성
-  인접리스트
-  노드 번호 입력 시 1씩 뺌
-  입력받을 때 한 노드 당 연결되는 정점이 모두 주어지므로 간선 연결 시 한 번씩 연결
-  BFS를 두 번 실행
  1)  첫 번째에는 시작 정점이 0
  2)  두 번째에는 시작 정점이 이전에 0에서 젤 먼 거리였던 끝 정점
-  큐로 트리를 탐색하면서 간선으로 연결된 거리의 합을 구해가며 가장 먼 거리(d_max)를 갱신