[백준] 1167 트리의 지름 (JAVA)

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

1167번: 트리의 지름

 

 

1. 문제 분석

해당 문제는, 트리에서 정점간의 거리가 가장 큰 두 정점을 찾는 문제이다.

 

그래프 단면

위 그림에서, 각 정점에서 거리가 가장 먼 두 정점을 구하면 다음과 같다.

1 ---> 5 = 11

2 ---> 5 = 10

3 ---> 5 = 9

4 ---> 5 = 6 

5- --> 1 = 11

 

이를 보면 모든 정점에서부터 최장 정점은 항상, 1 혹은 5를 포함하는 것을 알 수있다.

 

또한, 트리의 특성상, 모든 정점은 사이클이 없이 연결되어있고 한 정점에서 다른 정점으로 가는 경로는 유일하다.

 

임의의 한 정점에서, 거리가 먼 정점을 구해서, 그 정점을 기준으로 다시 정점이 최대인 노드를 구하면, 최종 distance가 큰 값을 출력하면 된다.

 

그래프를 인접리스트에 저장한 모습

위 그림은 각 노드를 인접리스트로 저장한 모습을 나타낸다.

(Node 번호, 가중치) 형태로 저장되어있고, 이러한 노드를 구현하기 위해

 

Node번호와 가중치를 인스턴스로 갖는 새로운 클래스를 정의해야한다.

 

 

 

2. 코드 구현

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 Main {
	
	static int  N;
	static ArrayList<edge>[] A; // 인접리스트를 담을 배열 A
	static boolean[] visited; // 방문 기록 배열에 저장
	static int[] distance; // 거리배열 저장
	
   public static void main(String[] args) throws IOException{	
		
	   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine()); // 노드 개수 입력받기
		A = new ArrayList[N+1];
		// 인접리스트 초기화
		for(int i=1; i<=N; i++) {
			A[i] = new ArrayList<edge>();
		}
		
		visited = new boolean[N+1];
		distance = new int[N+1];
		
		for(int i=0; i<N; i++) { // 그래프 데이터 저장하기
			StringTokenizer st = new StringTokenizer(br.readLine());
			int S = Integer.parseInt(st.nextToken());
			while(true) {
				int E = Integer.parseInt(st.nextToken());
				if(E==-1) {
					break;
				}
				int value = Integer.parseInt(st.nextToken());
				A[S].add(new edge(E,value));
			}
		}
	    
		BFS(1); //임의의 점을 시작점으로 BFS 실행하기
	    
		int Max = 1;
	    
	    for(int i=2; i<=N; i++) {
	    	if(distance[Max] < distance[i]) {
	    		Max = i;
	    	} 
	    }
	    distance = new int[N+1];
	    visited = new boolean[N+1];
	    BFS(Max); // 새로운 시작점으로 실행
	    Arrays.sort(distance);
	    System.out.println(distance[N]);
	}

	
	private static void BFS(int now) {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(now);
		visited[now] = true;
		while(!queue.isEmpty()) {
			int now_Node = queue.poll();
			for(edge i : A[now_Node]) {
				int e = i.edge;
				int v = i.value;
				if(!visited[e]) { // 방문하지 않은, Edge에 대해
				    visited[e] = true; // 방문 체크
				    queue.add(e);
				    distance[e] = distance[now_Node] + v; // 거리 배열 업데이트하기
				}
			  }
		    }	
	      }
}

	class edge {
		int edge; // 목적지 노드
		int value; // 에지의 가중치
		public edge(int edge, int value) {
			this.edge = edge;
			this.value = value;
		}
	}