백준 1967 트리의 지름(JAVA)

 

풀이방법

---

트리의 지름이란 트리를 가장 넓게 펼쳣을때 가장 긴 길이를 뜻한다.

따라서 dfs를 이용해 각 점에서 시작했을 때 합산하여 가장 가중치가 높은 부분을 출력하면 된다.

트리를 구현하기 위해 배열이나 어레이리스트를 사용할 수 있다.

나는 지금까지 배열을 통해서 구현해보았는데 배열을 사용하게 되면 2차원 배열로써 사용하지 않는 부분은 다 0으로 공간낭비가 심한 느낌이 들었다.

그래서 가변적인 어레이리스트로 구현을 했고. 이를 이해를 돕기 위해 그림으로 설명하자면 이렇다.

 

이런식으로 회색 안에있는 숫자는 시작점을 나타내고 그 아래 node 들은 어디로 연결되어있는지 정보를 나타낸다.

회색 안에 있는 시작점은 배열로 더 이상 늘어나지도 줄어들지도 않기 때문에 일반 배열로 생성해주고

 

각 배열 안에 들어가는 node 들은 몇개가 들어가는지 모르기 때문에 가변적으로 ArrayList 를 사용한다. 또한 node 클래스를 따로 구현하여 삽입해준다.

 

각 배열에 있는 인덱스를 시작점으로 dfs를 돌리면서 최대값을 갱신해주면 정답 출력이 가능하다.

 

코드

---

package pro;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class test9 {
	static class Node{
		int num, length;
		public Node(int num, int length) {
			this.num = num;
			this.length = length;
		}
	}
	static List<Node> list[];
	static int answer;
	static boolean visit[];
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	int T = Integer.parseInt(br.readLine());
    	list = new ArrayList[T+1];
    	for(int i = 1 ; i< T+1; i++) {
    		list[i] = new ArrayList<Node>();
    	}
    	for(int i =0 ; i< T-1; i++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		int start = Integer.parseInt(st.nextToken());
    		int end = Integer.parseInt(st.nextToken());
    		int length = Integer.parseInt(st.nextToken()); // 위의 length 랑 다른거임.
    		//양 쪽 노드 둘 다에 추가해줌.
    		list[start].add(new Node(end, length)); // 한 점에 두가지 정보가 들어있는 상태.
    		list[end].add(new Node(start, length)); //반대로도 추가해줘야함.
    		
    	}
    	answer = 0;
    	for(int i = 1; i<= T ;i ++) {
    		// 배열 생성 후 초기화 해주는 부분.
    		visit = new boolean[T+1]; //list[] 배열과 대응되면서 방문했는지 안했는지 체크해야함.
    		visit[i] = true; // 처음 시작점은 방문 true 로 잡고 시작함.
    		dfs(i, 0); // i 는 시작점. 0 은 가중치들의 합.
    	}
    	System.out.println(answer);
    	
    }

	private static void dfs(int start, int sum) {
		for(Node node : list[start]) {
			if(!visit[node.num]) {
				visit[node.num] = true;
				dfs(node.num, sum + node.length);
			}
		}
		answer = answer<=sum?sum:answer;
		
		
	}
}